Mohd__Messi

Hackerearth problem -The Chocolate Boy

Apr 7th, 2021
161
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define vi vector<int>
  3. #define ll long long
  4. using namespace std;
  5. ll dp[1002][1002];
  6. vector<ll> v1,v2;
  7. ll knapsack(int n,int m,int flag)
  8. {
  9.   if(m<0)
  10.    return INT_MIN;
  11.   if(n==0)
  12.    return 0;
  13.   if(dp[n][m]!=-1)
  14.    return dp[n][m];
  15.    
  16.   if(flag==0)
  17.     return dp[n][m]=max(v2[n-1]+knapsack(n-1,m-v1[n-1],0),max(v2[n-1]+knapsack(n-1,m-v1[n-1]/2,1),knapsack(n-1,m,0)));
  18.   else
  19.     return dp[n][m]=max(v2[n-1]+knapsack(n-1,m-v1[n-1],1),knapsack(n-1,m,1));  
  20.  
  21. }
  22. int main()
  23. {
  24.     int n,m;
  25.     cin>>n>>m;
  26.     string s[n];
  27.     char d[n];int a[n],b[n];
  28.     for(int i=0;i<n;i++)
  29.      cin>>s[i]>>d[i]>>a[i]>>b[i];
  30.     for(int i=0;i<=n;i++)
  31.     {
  32.         for(int j=0;j<=m;j++)
  33.          dp[i][j]=-1;
  34.     }
  35.     for(int i=0;i<n;i++)
  36.     {
  37.       if(d[i]=='S')
  38.       {
  39.         v1.push_back(a[i]);
  40.         v2.push_back(b[i]);
  41.         }      
  42.     }
  43.     int n1=v1.size();
  44.     cout<<knapsack(n1,m,0);
  45.     return 0;
  46. }
RAW Paste Data