Submission #1251005

#TimeUsernameProblemLanguageResultExecution timeMemory
1251005LaMatematica14Knapsack (NOI18_knapsack)C++20
37 / 100
1 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 = min(S, w-1); i >= 0; i--) aus[i] = vfw[i]; }; for (int i = 0; i < N; i++) { long long V, W, K; cin >> V >> W >> K; for (long long 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 << "\n"; }
#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...