TLE error on scuba diver problem on spoj

Правка en2, от maverick06, 2020-11-15 13:46:58

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

Here is my solution:

#include <bits/stdc++.h>
using namespace std;
//oxy,nitro,weight,n,ov,nv
int knapsack(vector<int>oxy,vector<int>nitro,vector<int>weight,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);
		vector<int>oxy(n);
		vector<int>nitro(n);
		vector<int>weight(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?

Теги #dp, #spoj, #cpp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский maverick06 2020-11-15 13:46:58 60
en1 Английский maverick06 2020-11-15 13:46:04 1489 Initial revision (published)