TLE error on scuba diver problem on spoj

Revision en1, by maverick06, 2020-11-15 13:46:04

Here is the link to the question: https://www.spoj.com/problems/SCUBADIV/

Here is my solution:

However it is giving tle .. Can someone help please? ~~~~~

include <bits/stdc++.h>

using namespace std; //oxy,nitro,weight,n,ov,nv int knapsack(vectoroxy,vectornitro,vectorweight,int n,int ov,int nv,map<string,int>&mp) { string key = to_string(ov)+"|"+to_string(nv)+"|"+to_string(n); if(n <= 0 && (ov>0 || nv>0)) { return 999999; // all cylinders explored } if(ov <= 0 && nv <= 0) { return 0; // base condition } if(mp.find(key)!=mp.end()) { return mp[key];// already explored part } return mp[key] = min(knapsack(oxy,nitro,weight,n-1,ov,nv,mp),weight[n-1]+knapsack(oxy,nitro,weight,n-1,max(ov-oxy[n-1],0),max(nv-nitro[n-1],0),mp)); // find min weight.

}

int main() { // your code goes here ios_base::sync_with_stdio(false); cin.tie(NULL); int t; scanf("%d",&t); while(t--) { int ov,nv; scanf("%d%d",&ov,&nv); int n; scanf("%d",&n); vectoroxy(n); vectornitro(n); vectorweight(n); for(int i=0;i<n;i++) { int ox,nx,w; scanf("%d%d%d",&ox,&nx,&w); oxy[i] = ox; nitro[i] = nx; weight[i] = w; } map<string,int>mp; // c<<knapsack(oxy,nitro,weight,n,ov,nv,mp)<<endl; printf("%d\n",knapsack(oxy,nitro,weight,n,ov,nv,mp)); } return 0; }

~~~~~

However it is giving tle .. Can someone help please?

Tags #dp, #spoj, #cpp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English maverick06 2020-11-15 13:46:58 60
en1 English maverick06 2020-11-15 13:46:04 1489 Initial revision (published)