Submission #1172431

#TimeUsernameProblemLanguageResultExecution timeMemory
1172431manowoKnapsack (NOI18_knapsack)C++20
49 / 100
458 ms327680 KiB
#include <bits/stdc++.h> using namespace std; const int M = 100004; const int N = 2004; vector<pair<int, int>> p; long long s, n, w, v, k, dp[N]; int main() { cin >> s >> n; if (n == 1) { cin >> v >> w >> k; cout << v * min(k, s / w) << endl; } else { for (int i = 0; i < n; i++) { cin >> v >> w >> k; while (k--) { p.push_back({v, w}); } } for (auto [v, w] : p) { for (int j = s; j >= w; j--) { dp[j] = max(dp[j], dp[j - w] + v); } } long long ans = 0; for (int i = 1; i <= s; i++) { ans = max(ans, dp[i]); } cout << ans << endl; } 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...