Submission #1192486

#TimeUsernameProblemLanguageResultExecution timeMemory
1192486dprtoKnapsack (NOI18_knapsack)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_S = 2005; long long dp[MAX_S]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; fill(dp, dp + S + 1, -1); dp[0] = 0; for (int i = 0; i < N; ++i) { int w, v, k; cin >> w >> v >> k; // Cập nhật DP ngược với số lượng tối đa k for (int s = S; s >= w; --s) { if (dp[s - w] != -1) { for (int cnt = 1; cnt <= k && s >= cnt * w; ++cnt) { if (dp[s - cnt * w] != -1) { dp[s] = max(dp[s], dp[s - cnt * w] + cnt * v); } } } } } long long max_value = *max_element(dp, dp + S + 1); cout << max_value << 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...