Submission #1131235

#TimeUsernameProblemLanguageResultExecution timeMemory
1131235physictypeKnapsack (NOI18_knapsack)C++20
73 / 100
278 ms327680 KiB
#include <bits/stdc++.h> using namespace std; int main() { int s,n; cin >> s >> n; vector<int> weights(n); vector<int> values(n); vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> values[i] >> weights[i] >> nums[i]; } vector<vector<int> > dp(n+1,vector<int>(s+1,0)); for (int i = 0; i <= s; i++) { dp[0][i]=0; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= s; j++) { dp[i][j]=dp[i-1][j]; for (int k = 1; k <= nums[n-i]; k++) { if (j>=weights[n-i]*k) { dp[i][j]=max(dp[i][j],dp[i-1][j-weights[n-i]*k]+values[n-i]*k); } else { break; } } } } cout << dp[n][s]; }
#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...