Submission #988821

#	Time	Username	Problem	Language	Result	Execution time	Memory
988821		steph2006	Knapsack (NOI18_knapsack)	C++14	37 / 100	1032 ms	1116 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
signed main(){
  fastio();
// #ifndef ONLINE_JUDGE
// freopen("input1.txt","r",stdin);
//     freopen("output1.txt","w",stdout);
//     #endif
    //games and constructive mein hamesha test cases banakar dekho aur unpe solve karne ki
    //koshish karo.recursive approach type.
    int s,n; cin>>s>>n;
    vector<vector<int>>v(n+1,vector<int>(3));
    for(int i=1; i<=n; i++){
      int a,b,c;
      cin>>a>>b>>c;
      v[i][0]=a;v[i][1]=b;v[i][2]=c;
    }
    int dp[n+1][s+1];
    for(int i=0; i<=n; i++){
      for(int j=0; j<=s; j++){
        dp[i][j]=0;
      }
    }
    for(int i=1; i<=n; i++){
      for(int j=1; j<=s; j++){
        for(int k=0; k<=v[i][2]; k++){
          if(j>=(k*v[i][1])){
            dp[i][j]=max(dp[i][j],dp[i-1][j-(k*v[i][1])]+k*v[i][0]);
          }
        }
      }
    }
    cout<<dp[n][s]<<endl;



    


              
  

return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27