Submission #1131254

#TimeUsernameProblemLanguageResultExecution timeMemory
1131254nlknKnapsack (NOI18_knapsack)C++20
29 / 100
2 ms328 KiB
#include <iostream> #include <vector> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> m >> n; int v[n],w[n],k[n]; for(int i=0; i<n; i++)cin>>v[i]>>w[i]>>k[i]; vector<int> prev(m+1); for(int j=0; j<=m; j++)prev[j]=0; for(int j=1; j<=k[0]&&j*w[0]<=m; j++){ prev[j*w[0]]=v[0]*j; } //for(int j=0; j<=m; j++)cout<<dp[0][j]<<" "; //cout<<endl; for(int i=1; i<n; i++){ vector<int> curr(m+1); for(int j=0; j<=m; j++)curr[j]=prev[j]; int j=0; for(; j+k[i]*w[i]<=m; j++){ for(int l=1; l<=k[i]&&j+l*w[i]<=m; l++){ curr[j+l*w[i]]=max(curr[j+l*w[i]],prev[j]+v[i]*l); } } j++; for(; j+w[i]<=m; j++){ curr[j+w[i]]=max(curr[j+w[i]],curr[j]+v[i]); } prev=curr; //for(int j=0; j<=m; j++)cout<<dp[i][j]<<" "; //cout<<endl; } int ans=0; for(int i=0; i<=m; i++)ans=max(ans,prev[i]); cout<<ans; }
#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...