#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |