Submission #1172356

#TimeUsernameProblemLanguageResultExecution timeMemory
1172356toplion7Knapsack (NOI18_knapsack)C++20
49 / 100
1096 ms500 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXXX = 1e4 + 5; vector<int> dp(MAXXX); signed main() { int n, k; cin >> k >> n; vector<int> a(n); vector<int> b(n); vector<int> c(n); for (int i = 0; i < n; i++) { cin >> b[i] >> a[i] >> c[i]; } for (int i = 0; i < MAXXX; i++) { dp[i] = 0; } if(n == 1) { int cnt = k / a[0]; cout << min(c[0], cnt) * b[0]; return 0; } for (int i = 0; i < n; i++) { for(int j = MAXXX - 1; j >= a[i]; j--) { for(int K = 0; K <= c[i]; K++) { if(j >= a[i]* K) dp[j] = max(dp[j], dp[j - a[i] * K] + b[i] * K); } } } int mx = 0; for(int i = 0; i <= k; i++) { mx = max(mx, dp[i]); } cout << mx; 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...