Submission #1217322

#TimeUsernameProblemLanguageResultExecution timeMemory
1217322jonatas57Knapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1608 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]; vi last(s + 1, 0); vi curr(s + 1, -1); loop(n) { vector<maxqueue> qs(ws[i]); 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]) { qs[k].push(last[j]); curr[j] = qs[k].max(); qs[k].del += vs[i]; if (qs[k].size() > ks[i]) qs[k].pop(); } last.swap(curr); } cout << last[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...