Submission #1131248

#TimeUsernameProblemLanguageResultExecution timeMemory
1131248nlknKnapsack (NOI18_knapsack)C++20
73 / 100
282 ms327680 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; int main() { 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]; int dp[n][m+1]; for(int j=0; j<=m; j++)dp[0][j]=0; for(int j=1; j<=k[0]&&j*w[0]<=m; j++){ dp[0][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++){ for(int j=0; j<=m; j++)dp[i][j]=dp[i-1][j]; for(int j=0; j<=m; j++){ for(int l=1; l<=k[i]&&j+l*w[i]<=m; l++){ dp[i][j+l*w[i]]=max(dp[i][j+l*w[i]],dp[i-1][j]+v[i]*l); } } //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,dp[n-1][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...