Submission #1170291

#TimeUsernameProblemLanguageResultExecution timeMemory
1170291yamiza_zinnoKnapsack (NOI18_knapsack)C++20
37 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 5; long long dp[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int s, n; cin >> s >> n; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; vector<int> item; for (int j = 1; k > 0; j *= 2) { int take = min(j, k); item.push_back(take); k -= take; } for (int take : item) { for (int j = s; j >= take * w; j--) { dp[j] = max(dp[j], dp[j - take * w] + take * v); } } } 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...