Submission #1251018

#TimeUsernameProblemLanguageResultExecution timeMemory
1251018LaMatematica14Knapsack (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), aus(S+1); auto upd = [&](int v, int w) { for (int i = S; i >= 0; i--) { aus[i] = vfw[i]; if (i >= w) aus[i] = max(vfw[i], vfw[i-w]+v); } swap(vfw, aus); }; for (int i = 0; i < N; i++) { long long V, W, K; cin >> V >> W >> K; for (long long k = 1; k <= K; K-=k, k<<=1) upd(V*k, W*k); if (K > 0) upd(V*K, W*K); } long long best = 0; for (long long i : vfw) best = max(best, 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...