Submission #1198197

#TimeUsernameProblemLanguageResultExecution timeMemory
1198197almaharbas4Knapsack (NOI18_knapsack)C++20
12 / 100
1 ms328 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; int main() { int n,k; cin>>k>>n; vector<int> val(n),w(n),cap(n); for(int i=0;i<n;i++) { cin>>val[i]>>w[i]>>cap[i]; } vector<vector<ll>> dp(n+1,vector<ll>(k+1,-1)); dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=k;j++) { for(int a=1;a<=cap[i-1]&&j-a*w[i-1]>=0;a++) { if(dp[i-1][j-a*w[i-1]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-a*w[i-1]]+a*val[i-1]); else dp[i][j]=max(dp[i][j],(ll)a*val[i-1]); } } } cout<<dp[n][k]<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...