Submission #1254831

#TimeUsernameProblemLanguageResultExecution timeMemory
1254831goutomKnapsack (NOI18_knapsack)C++20
37 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<int> dp(S + 1, 0); for (int i = 0; i < N; i++) { int V, W; long long K; cin >> V >> W >> K; long long count = 1; while (K > 0) { long long take = min(count, K); int val = V * (int)take; int wt = W * (int)take; for (int w = S; w >= wt; w--) { dp[w] = max(dp[w], dp[w - wt] + val); } K -= take; count <<= 1; } } cout << dp[S] << "\n"; 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...