Submission #1275988

#TimeUsernameProblemLanguageResultExecution timeMemory
1275988lee.desmond2016Knapsack (NOI18_knapsack)C++20
73 / 100
1096 ms15836 KiB
#include <bits/stdc++.h> using namespace std; struct Item { long long v, w; // use long long to avoid overflow }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<Item> items; items.reserve(N * 30); // prevent realloc overhead for (int i = 0; i < N; i++) { long long V, W, K; cin >> V >> W >> K; for (long long p = 1; K > 0; p <<= 1) { long long cnt = min(p, K); items.push_back({V * cnt, W * cnt}); K -= cnt; } } vector<long long> dp(S + 1, 0); for (auto &it : items) { for (int j = S; j >= it.w; j--) { dp[j] = max(dp[j], dp[j - it.w] + it.v); } } cout << dp[S] << "\n"; }
#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...