Submission #1014814

#TimeUsernameProblemLanguageResultExecution timeMemory
1014814KindaGoodGamesKnapsack (NOI18_knapsack)C++14
29 / 100
2 ms600 KiB
#include <bits/stdc++.h> #define ll long long //#define int ll #define pii pair<int, int> #define tiii tuple<int, int, int> using namespace std; int32_t main() { int n, s; cin >> s >> n; vector<int> value(n), weight(n), capacity(n); vector<int> dp(s); for (int i = 0; i < n; i++) { cin >> value[i] >> weight[i] >> capacity[i]; } if(n == 1){ cout << min(s/weight[0], capacity[0]) * value[0]; return 0; } for (int i = 0; i < n; i++) { for (int j = s; j > 0; j--) { //dp[j] = max(dp[j],dp[j - 1]); if (j < weight[i]) continue; for (int k = 1; k <= capacity[i]; k++) { if(j-(k*weight[i]) < 0) break; if(dp[j] <dp[j - (k*weight[i])] + (k*value[i])){ dp[j] = dp[j - (k*weight[i])] + (k*value[i]); }else{ break; } } } } int ma = 0; for(int i = 0; i <= s; i++){ ma = max(ma, dp[i]); } cout << ma; }
#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...