Submission #1250897

#TimeUsernameProblemLanguageResultExecution timeMemory
1250897LaMatematica14Knapsack (NOI18_knapsack)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int N, S; cin >> S >> N; vector<long long> vfw(S+1, 0); vector<long long> aus(S+1); auto upd = [&](int v, int w) { for (int i = S; i >= w; i--) { aus[i] = max(vfw[i], vfw[i-w]+v); } }; for (int i = 0; i < N; i++) { int V, W, K; cin >> V >> W >> K; fill(aus.begin(), aus.end(), 0); for (int k = 1; k <= K; k<<=1) { upd(V*k, W*k); K-=k; vfw = aus; } if (K > 0) upd(V*K, W*K); vfw = aus; } long long best = 0; for (int i = 0; i <= S; i++) { best = max(best, vfw[i]); } cout << best; }
#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...