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?

I had been trying to solve these problem from last three hours but I am not able to find where my code is giving tle . Please help to find where I am wrong.

Here is the problem: https://www.spoj.com/problems/FARIDA/

Here is my code:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	// your code goes here
	ll t;
	cin>>t;
	ll k=1;
	while(t--)
	{
		ll n;
		cin>>n;
		vector<ll>arr;
		for(int i=0;i<n;i++)
		{
			ll num;
			cin>>num;
			arr.push_back(num);
		}
		ll dp[10000];
		dp[0] = 0;
		dp[1]=arr[0];
		if(n == 0)
		{
			printf("Case %d: %d\n",k,0);
		}
		if(n == 1)
		{
			printf("Case %d: %lld\n",k,dp[1]);
			continue;
		}
		dp[2] = max(arr[1],arr[2]);
		for(ll i=3;i<=n;i++)
		{
			dp[i] = max(arr[i-1]+dp[i-2],dp[i-1]);
		}
	   printf("Case %d: %lld\n",k,dp[n]);
	   k++;
	}
	
	return 0;
}

Thanks :)

Here is the link to the problem : https://www.spoj.com/problems/RPLB/

Here is my code however it is giving tle:

#include <bits/stdc++.h>
using namespace std;
int dp[20001][20001];
int knapsack(int n,int s,vector<int>a)
{
	if(n <= 0 || s<0)
	{
		return 0;
	}
    if(dp[n][s]!=-1)
    {
    	return dp[n][s];
    }
	if(a[n-1]<=s)
	{
		return dp[n][s] = max(a[n-1]+knapsack(n-2,s-a[n-1],a),knapsack(n-1,s,a));
	}
	else
	{
		return dp[n][s] = knapsack(n-1,s,a);
	}
}

int main() {
	// your code goes here
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		int n,s;
		scanf("%d%d",&n,&s);
		vector<int>a(n);
		for(int i=0;i<n;i++)
		{
			int num;
			scanf("%d",&num);
			a[i] = num;
		}
		memset(dp,-1,sizeof(dp));
		int ans = knapsack(n,s,a);
		//cout<<ans<<endl;
		printf("Scenario #%d: %d\n",i,ans);
	}
}

Thanks:)

Here is the link to the problem: https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/parwal-problem/ What should be approach and how can I solve these problem?