Submission #1255206

#TimeUsernameProblemLanguageResultExecution timeMemory
1255206msiyemKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; #define optimize() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define PB push_back int main() { optimize(); int S, N; cin >> S >> N; vl dp(S + 1, 0); for (int i = 0; i < N; ++i) { ll v, w, k; cin >> v >> w >> k; // Binary representation trick to break into log(k) items for (ll t = 1; k > 0; t <<= 1) { ll use = min(t, k); k -= use; ll tw = w * use; ll tv = v * use; // 0/1 knapsack step for (int j = S; j >= tw; --j) { dp[j] = max(dp[j], dp[j - tw] + tv); } } } 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...