# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
983760 | 2024-05-16T04:48:57 Z | Peter2017 | Knapsack (NOI18_knapsack) | C++17 | 1000 ms | 2908 KB |
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define pill pair<int,ll> #define mem(a, b) memset(a, b, sizeof(a)) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define name "test" using namespace std; const int N = 1e5 + 5; const int S = 2e3 + 5; const int mod = 1e9 + 7; template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;} template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;} struct item{ int v, w, k; }; int n; int s; ll f[2][S]; item a[N]; ll Max[S]; deque<ll> dq[S]; void load(){ cin.tie(0)->sync_with_stdio(0); if (fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } } void input(){ cin >> s >> n; for (int i = 1; i <= n; i++) cin >> a[i].v >> a[i].w >> a[i].k; } void solve(){ for (int i = 1; i <= n; i++){ bool cur = (i & 1); bool pre = (cur ^ 1); for (int j = 0; j < a[i].w; j++){ while (dq[j].size()) dq[j].pop_back(); dq[j].push_back(j); maxi(f[cur][j], f[pre][j]); } for (int j = a[i].w; j <= s; j++){ int p = j % a[i].w; while (dq[p].size() && (j - dq[p].front()) / a[i].w > a[i].k) dq[p].pop_front(); maxi(f[cur][j], f[pre][dq[p].front()] + 1ll * ((j - dq[p].front()) / a[i].w) * a[i].v); maxi(f[cur][j], f[cur][j - 1]); maxi(f[cur][j], f[pre][j]); while (dq[p].size()){ int id = dq[p].back(); if (f[pre][id] - 1ll * ((id - p) / a[i].w) * a[i].v <= f[pre][j] - 1ll * ((j - p) / a[i].w) * a[i].v) dq[p].pop_back(); else break; } dq[p].push_back(j); } } cout << f[n & 1][s]; } int main(){ load(); input(); solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1624 KB | Output is correct |
2 | Correct | 1 ms | 1624 KB | Output is correct |
3 | Correct | 1 ms | 1628 KB | Output is correct |
4 | Correct | 1 ms | 1628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1624 KB | Output is correct |
2 | Correct | 7 ms | 1628 KB | Output is correct |
3 | Correct | 7 ms | 1844 KB | Output is correct |
4 | Correct | 2 ms | 1628 KB | Output is correct |
5 | Correct | 2 ms | 1628 KB | Output is correct |
6 | Correct | 4 ms | 1628 KB | Output is correct |
7 | Correct | 4 ms | 1628 KB | Output is correct |
8 | Correct | 3 ms | 1784 KB | Output is correct |
9 | Correct | 4 ms | 1628 KB | Output is correct |
10 | Correct | 4 ms | 1628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1624 KB | Output is correct |
2 | Correct | 7 ms | 1628 KB | Output is correct |
3 | Correct | 7 ms | 1844 KB | Output is correct |
4 | Correct | 2 ms | 1628 KB | Output is correct |
5 | Correct | 2 ms | 1628 KB | Output is correct |
6 | Correct | 4 ms | 1628 KB | Output is correct |
7 | Correct | 4 ms | 1628 KB | Output is correct |
8 | Correct | 3 ms | 1784 KB | Output is correct |
9 | Correct | 4 ms | 1628 KB | Output is correct |
10 | Correct | 4 ms | 1628 KB | Output is correct |
11 | Correct | 1 ms | 1628 KB | Output is correct |
12 | Correct | 7 ms | 1628 KB | Output is correct |
13 | Correct | 7 ms | 1628 KB | Output is correct |
14 | Correct | 2 ms | 1628 KB | Output is correct |
15 | Correct | 2 ms | 1628 KB | Output is correct |
16 | Correct | 3 ms | 1628 KB | Output is correct |
17 | Correct | 4 ms | 1884 KB | Output is correct |
18 | Correct | 4 ms | 1860 KB | Output is correct |
19 | Correct | 4 ms | 1628 KB | Output is correct |
20 | Correct | 3 ms | 1628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1624 KB | Output is correct |
2 | Correct | 1 ms | 1624 KB | Output is correct |
3 | Correct | 1 ms | 1628 KB | Output is correct |
4 | Correct | 1 ms | 1628 KB | Output is correct |
5 | Correct | 1 ms | 1624 KB | Output is correct |
6 | Correct | 7 ms | 1628 KB | Output is correct |
7 | Correct | 7 ms | 1844 KB | Output is correct |
8 | Correct | 2 ms | 1628 KB | Output is correct |
9 | Correct | 2 ms | 1628 KB | Output is correct |
10 | Correct | 4 ms | 1628 KB | Output is correct |
11 | Correct | 4 ms | 1628 KB | Output is correct |
12 | Correct | 3 ms | 1784 KB | Output is correct |
13 | Correct | 4 ms | 1628 KB | Output is correct |
14 | Correct | 4 ms | 1628 KB | Output is correct |
15 | Correct | 1 ms | 1628 KB | Output is correct |
16 | Correct | 7 ms | 1628 KB | Output is correct |
17 | Correct | 7 ms | 1628 KB | Output is correct |
18 | Correct | 2 ms | 1628 KB | Output is correct |
19 | Correct | 2 ms | 1628 KB | Output is correct |
20 | Correct | 3 ms | 1628 KB | Output is correct |
21 | Correct | 4 ms | 1884 KB | Output is correct |
22 | Correct | 4 ms | 1860 KB | Output is correct |
23 | Correct | 4 ms | 1628 KB | Output is correct |
24 | Correct | 3 ms | 1628 KB | Output is correct |
25 | Correct | 1 ms | 1624 KB | Output is correct |
26 | Correct | 5 ms | 1624 KB | Output is correct |
27 | Correct | 7 ms | 1628 KB | Output is correct |
28 | Correct | 2 ms | 1628 KB | Output is correct |
29 | Correct | 2 ms | 1628 KB | Output is correct |
30 | Correct | 4 ms | 1628 KB | Output is correct |
31 | Correct | 4 ms | 1624 KB | Output is correct |
32 | Correct | 4 ms | 1628 KB | Output is correct |
33 | Correct | 4 ms | 1624 KB | Output is correct |
34 | Correct | 3 ms | 1628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1624 KB | Output is correct |
2 | Correct | 1 ms | 1624 KB | Output is correct |
3 | Correct | 1 ms | 1628 KB | Output is correct |
4 | Correct | 1 ms | 1628 KB | Output is correct |
5 | Correct | 1 ms | 1624 KB | Output is correct |
6 | Correct | 7 ms | 1628 KB | Output is correct |
7 | Correct | 7 ms | 1844 KB | Output is correct |
8 | Correct | 2 ms | 1628 KB | Output is correct |
9 | Correct | 2 ms | 1628 KB | Output is correct |
10 | Correct | 4 ms | 1628 KB | Output is correct |
11 | Correct | 4 ms | 1628 KB | Output is correct |
12 | Correct | 3 ms | 1784 KB | Output is correct |
13 | Correct | 4 ms | 1628 KB | Output is correct |
14 | Correct | 4 ms | 1628 KB | Output is correct |
15 | Correct | 1 ms | 1628 KB | Output is correct |
16 | Correct | 7 ms | 1628 KB | Output is correct |
17 | Correct | 7 ms | 1628 KB | Output is correct |
18 | Correct | 2 ms | 1628 KB | Output is correct |
19 | Correct | 2 ms | 1628 KB | Output is correct |
20 | Correct | 3 ms | 1628 KB | Output is correct |
21 | Correct | 4 ms | 1884 KB | Output is correct |
22 | Correct | 4 ms | 1860 KB | Output is correct |
23 | Correct | 4 ms | 1628 KB | Output is correct |
24 | Correct | 3 ms | 1628 KB | Output is correct |
25 | Correct | 1 ms | 1624 KB | Output is correct |
26 | Correct | 5 ms | 1624 KB | Output is correct |
27 | Correct | 7 ms | 1628 KB | Output is correct |
28 | Correct | 2 ms | 1628 KB | Output is correct |
29 | Correct | 2 ms | 1628 KB | Output is correct |
30 | Correct | 4 ms | 1628 KB | Output is correct |
31 | Correct | 4 ms | 1624 KB | Output is correct |
32 | Correct | 4 ms | 1628 KB | Output is correct |
33 | Correct | 4 ms | 1624 KB | Output is correct |
34 | Correct | 3 ms | 1628 KB | Output is correct |
35 | Correct | 20 ms | 2908 KB | Output is correct |
36 | Execution timed out | 1067 ms | 2908 KB | Time limit exceeded |
37 | Halted | 0 ms | 0 KB | - |