#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pli = pair<lint, int>;
const int MAX_N = 1e5 + 5, MAX_S = 2000 + 5;
int s, n;
lint v[MAX_N];
int w[MAX_N], k[MAX_N];
lint dp[MAX_N][MAX_S];
priority_queue<pli> trans[MAX_S];
int main() {
// freopen("knapsack.in", "r", stdin);
cin >> s >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> k[i];
k[i] = min(k[i], s);
}
for (int i = n; i >= 1; i--) {
for (int c = 0; c <= s; c++) {
if (c < w[i]) {
while (trans[c].size())
trans[c].pop();
trans[c].push({dp[i + 1][c], c});
dp[i][c] = dp[i + 1][c];
} else {
trans[c % w[i]].push({dp[i + 1][c] - v[i] * (c / w[i]), c});
while (trans[c % w[i]].top().second < c - k[i] * w[i]) // Should always have size
trans[c % w[i]].pop();
int new_c = trans[c % w[i]].top().second;
assert((c - new_c) % w[i] == 0);
dp[i][c] = dp[i + 1][new_c] + v[i] * ((c - new_c) / w[i]);
}
// cout << i << " " << c << ": " << dp[i][c] << endl;
}
}
cout << dp[1][s] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2908 KB |
Output is correct |
2 |
Correct |
6 ms |
4112 KB |
Output is correct |
3 |
Correct |
5 ms |
3932 KB |
Output is correct |
4 |
Correct |
3 ms |
4188 KB |
Output is correct |
5 |
Correct |
4 ms |
3932 KB |
Output is correct |
6 |
Correct |
5 ms |
4132 KB |
Output is correct |
7 |
Correct |
5 ms |
4188 KB |
Output is correct |
8 |
Correct |
4 ms |
4188 KB |
Output is correct |
9 |
Correct |
4 ms |
4036 KB |
Output is correct |
10 |
Correct |
5 ms |
4184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2908 KB |
Output is correct |
2 |
Correct |
6 ms |
4112 KB |
Output is correct |
3 |
Correct |
5 ms |
3932 KB |
Output is correct |
4 |
Correct |
3 ms |
4188 KB |
Output is correct |
5 |
Correct |
4 ms |
3932 KB |
Output is correct |
6 |
Correct |
5 ms |
4132 KB |
Output is correct |
7 |
Correct |
5 ms |
4188 KB |
Output is correct |
8 |
Correct |
4 ms |
4188 KB |
Output is correct |
9 |
Correct |
4 ms |
4036 KB |
Output is correct |
10 |
Correct |
5 ms |
4184 KB |
Output is correct |
11 |
Correct |
1 ms |
2908 KB |
Output is correct |
12 |
Correct |
11 ms |
4108 KB |
Output is correct |
13 |
Correct |
6 ms |
3956 KB |
Output is correct |
14 |
Correct |
3 ms |
4184 KB |
Output is correct |
15 |
Correct |
3 ms |
4188 KB |
Output is correct |
16 |
Correct |
5 ms |
4188 KB |
Output is correct |
17 |
Correct |
6 ms |
4208 KB |
Output is correct |
18 |
Correct |
7 ms |
4188 KB |
Output is correct |
19 |
Correct |
5 ms |
4188 KB |
Output is correct |
20 |
Correct |
5 ms |
4188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2560 KB |
Output is correct |
5 |
Correct |
1 ms |
2908 KB |
Output is correct |
6 |
Correct |
6 ms |
4112 KB |
Output is correct |
7 |
Correct |
5 ms |
3932 KB |
Output is correct |
8 |
Correct |
3 ms |
4188 KB |
Output is correct |
9 |
Correct |
4 ms |
3932 KB |
Output is correct |
10 |
Correct |
5 ms |
4132 KB |
Output is correct |
11 |
Correct |
5 ms |
4188 KB |
Output is correct |
12 |
Correct |
4 ms |
4188 KB |
Output is correct |
13 |
Correct |
4 ms |
4036 KB |
Output is correct |
14 |
Correct |
5 ms |
4184 KB |
Output is correct |
15 |
Correct |
1 ms |
2908 KB |
Output is correct |
16 |
Correct |
11 ms |
4108 KB |
Output is correct |
17 |
Correct |
6 ms |
3956 KB |
Output is correct |
18 |
Correct |
3 ms |
4184 KB |
Output is correct |
19 |
Correct |
3 ms |
4188 KB |
Output is correct |
20 |
Correct |
5 ms |
4188 KB |
Output is correct |
21 |
Correct |
6 ms |
4208 KB |
Output is correct |
22 |
Correct |
7 ms |
4188 KB |
Output is correct |
23 |
Correct |
5 ms |
4188 KB |
Output is correct |
24 |
Correct |
5 ms |
4188 KB |
Output is correct |
25 |
Correct |
1 ms |
2904 KB |
Output is correct |
26 |
Correct |
16 ms |
4188 KB |
Output is correct |
27 |
Correct |
6 ms |
3964 KB |
Output is correct |
28 |
Correct |
4 ms |
4188 KB |
Output is correct |
29 |
Correct |
3 ms |
4188 KB |
Output is correct |
30 |
Correct |
5 ms |
4184 KB |
Output is correct |
31 |
Correct |
5 ms |
4188 KB |
Output is correct |
32 |
Correct |
5 ms |
4188 KB |
Output is correct |
33 |
Correct |
5 ms |
4188 KB |
Output is correct |
34 |
Correct |
5 ms |
4188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2560 KB |
Output is correct |
5 |
Correct |
1 ms |
2908 KB |
Output is correct |
6 |
Correct |
6 ms |
4112 KB |
Output is correct |
7 |
Correct |
5 ms |
3932 KB |
Output is correct |
8 |
Correct |
3 ms |
4188 KB |
Output is correct |
9 |
Correct |
4 ms |
3932 KB |
Output is correct |
10 |
Correct |
5 ms |
4132 KB |
Output is correct |
11 |
Correct |
5 ms |
4188 KB |
Output is correct |
12 |
Correct |
4 ms |
4188 KB |
Output is correct |
13 |
Correct |
4 ms |
4036 KB |
Output is correct |
14 |
Correct |
5 ms |
4184 KB |
Output is correct |
15 |
Correct |
1 ms |
2908 KB |
Output is correct |
16 |
Correct |
11 ms |
4108 KB |
Output is correct |
17 |
Correct |
6 ms |
3956 KB |
Output is correct |
18 |
Correct |
3 ms |
4184 KB |
Output is correct |
19 |
Correct |
3 ms |
4188 KB |
Output is correct |
20 |
Correct |
5 ms |
4188 KB |
Output is correct |
21 |
Correct |
6 ms |
4208 KB |
Output is correct |
22 |
Correct |
7 ms |
4188 KB |
Output is correct |
23 |
Correct |
5 ms |
4188 KB |
Output is correct |
24 |
Correct |
5 ms |
4188 KB |
Output is correct |
25 |
Correct |
1 ms |
2904 KB |
Output is correct |
26 |
Correct |
16 ms |
4188 KB |
Output is correct |
27 |
Correct |
6 ms |
3964 KB |
Output is correct |
28 |
Correct |
4 ms |
4188 KB |
Output is correct |
29 |
Correct |
3 ms |
4188 KB |
Output is correct |
30 |
Correct |
5 ms |
4184 KB |
Output is correct |
31 |
Correct |
5 ms |
4188 KB |
Output is correct |
32 |
Correct |
5 ms |
4188 KB |
Output is correct |
33 |
Correct |
5 ms |
4188 KB |
Output is correct |
34 |
Correct |
5 ms |
4188 KB |
Output is correct |
35 |
Runtime error |
92 ms |
262144 KB |
Execution killed with signal 9 |
36 |
Halted |
0 ms |
0 KB |
- |