Submission #1133405

#TimeUsernameProblemLanguageResultExecution timeMemory
1133405mestiveKnapsack (NOI18_knapsack)C++20
73 / 100
1092 ms2080 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define MOD 998244353 #define ln '\n' struct Item { int value; int weight; int count; }; int main() { ios::sync_with_stdio(0); cin.tie(0); int s{}, n{}; cin >> s >> n; int v{}, w{}, c{}; vector<Item> items; vector<ll> dp(s+1, 0); for (int i = 0; i < n; ++i) { cin >> v >> w >> c; items.push_back({v, w, c}); for (int k = 1; c > 0; k *= 2) { int amount = min(k, c); if ((ll) w * amount > s) break; for (int j = s; j >= w * amount; j--) { dp[j] = max(dp[j], dp[j - w * amount] + (ll)v * amount); } c -= amount; } } cout << dp[s] << ln; 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...