Submission #1217327

#TimeUsernameProblemLanguageResultExecution timeMemory
1217327jonatas57Knapsack (NOI18_knapsack)C++20
73 / 100
1093 ms1616 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<bool> vb; typedef pair<int, int> ii; const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; #define each(x, s) for (auto& x : s) #define loop(x) for (int i = 0;i < x;i++) #define vloop(v, x) for (int v = 0;v < x;v++) #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define endl "\n" struct maxqueue { list<ii> q; int t = 0, head = 0; int del = 0; void push(int x) { while (!q.empty() and q.back().first < x - del) q.pop_back(); q.emplace_back(x - del, t++); } void pop() { head++; if (!q.empty() and q.front().second < head) q.pop_front(); } int max() { return q.empty() ? 0 : q.front().first + del; } int size() { return t - head; } }; int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int s, n; cin >> s >> n; vi vs(n), ws(n), ks(n); loop(n) cin >> vs[i] >> ws[i] >> ks[i]; vector<vi> dp(2, vi(s + 1, 0)); fill(iter(dp[1]), -1); int curr = 1; loop(n) { vector<maxqueue> qs(ws[i]); dp[curr][0] = 0; qs[0].push(0); qs[0].del += vs[i]; for (int j = 1, k = 1 % ws[i];j <= s;j++, k = k + 1 == ws[i] ? 0 : k + 1) { qs[k].push(dp[curr ^ 1][j]); dp[curr][j] = qs[k].max(); qs[k].del += vs[i]; if (qs[k].size() > ks[i]) qs[k].pop(); } curr ^= 1; } cout << dp[curr ^ 1][s] << endl; 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...