Submission #1133407

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