this is the problem https://www.spoj.com/problems/SCUBADIV/
this is my solution
#include<bits/stdc++.h>
#define VI vector <int>
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
typedef long long ll;
using namespace std;
int dp[22][80][1001];
int knapsack(int o2[],int n2[],int wt[],int n,int t,int a)
{
if(n==0||t==0||a==0)
{
return 0;
}
if(dp[t][a][n]!=-1)
return dp[t][a][n];
if(o2[n-1]>t && n2[n-1]>a)
return dp[t][a][n]=knapsack(o2,n2,wt,n-1,t,a);
if(o2[n-1]>t)
return dp[t][a][n]=wt[n-1]+knapsack(o2,n2,wt,n-1,t,a-n2[n-1]);
if(n2[n-1]>a)
return dp[t][a][n]=wt[n-1]+knapsack(o2,n2,wt,n-1,t-o2[n-1],a);
if(t>0 && a>0)
return dp[t][a][n]=wt[n-1]+knapsack(o2,n2,wt,n-1,t-o2[n-1],a-n2[n-1]);
if(t<0&& a>0)
return dp[t][a][n]=knapsack(o2,n2,wt,n-1,0,a);
if(t>0&& a<0)
return dp[t][a][n]=knapsack(o2,n2,wt,n-1,t,0);
if(t<0 && a<0)
return dp[t][a][n]=knapsack(o2,n2,wt,n-1,0,0);
}
int main()
{ memset(dp,-1,sizeof(dp));
int c;
cin>>c;
while(c--)
{
int t,a;
cin>>t>>a;
int n;
cin>>n;
int o2[n],n2[n],wt[n];
for(int i=0;i<n;i++)
cin>>o2[i]>>n2[i]>>wt[i];
cout<<knapsack(o2,n2,wt,n,t,a)<<endl;
}
}
I don\'t understand why is this giving wrong answer on submitting but passes the test case.
Here , I have taken a 3d dp having dimensions as oxygen , nitrogen,and weight of cylinder. Inside knapsack() arguments are o2 array,n2 array, wt array, size of array(n),oxygen need(t),nitrogen need(a).
Aucun commentaire:
Enregistrer un commentaire