# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
318711 | 2020-11-03T00:42:55 Z | ryangohca | Knapsack (NOI18_knapsack) | C++17 | 145 ms | 5228 KB |
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> priority_queue<pii> values[2001]; vector<pii> candidates; int dp[2001]; int32_t main() { int s, n; cin >> s >> n; for (int i = 0; i < n; i++){ int v, w, k; cin >> v >> w >> k; values[w].push({v, k}); } for (int i = 1; i <= 2000; i++){ int canChoose = s / i; while (!values[i].empty() && canChoose > 0){ pii top_e = values[i].top(); values[i].pop(); int num_chosen = min(canChoose, top_e.second); for (int j = 0; j < num_chosen; j++) candidates.push_back({top_e.first, i}); canChoose -= num_chosen; } } for (int a = 0; a < candidates.size(); ++a){ for (int c = s; c >= candidates[a].second; --c){ dp[c] = max(dp[c], dp[c - candidates[a].second] + candidates[a].first); } } cout << dp[s] << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 396 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 396 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 3 ms | 512 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 2 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 2 ms | 396 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 492 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 3 ms | 512 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 2 ms | 364 KB | Output is correct |
21 | Correct | 1 ms | 364 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 1 ms | 364 KB | Output is correct |
26 | Correct | 6 ms | 492 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 2 ms | 364 KB | Output is correct |
31 | Correct | 1 ms | 364 KB | Output is correct |
32 | Correct | 1 ms | 364 KB | Output is correct |
33 | Correct | 1 ms | 364 KB | Output is correct |
34 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 2 ms | 396 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 492 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 3 ms | 512 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 2 ms | 364 KB | Output is correct |
21 | Correct | 1 ms | 364 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 1 ms | 364 KB | Output is correct |
26 | Correct | 6 ms | 492 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 2 ms | 364 KB | Output is correct |
31 | Correct | 1 ms | 364 KB | Output is correct |
32 | Correct | 1 ms | 364 KB | Output is correct |
33 | Correct | 1 ms | 364 KB | Output is correct |
34 | Correct | 1 ms | 364 KB | Output is correct |
35 | Correct | 68 ms | 3416 KB | Output is correct |
36 | Correct | 88 ms | 3668 KB | Output is correct |
37 | Correct | 74 ms | 3520 KB | Output is correct |
38 | Correct | 78 ms | 3916 KB | Output is correct |
39 | Correct | 102 ms | 4372 KB | Output is correct |
40 | Correct | 145 ms | 5228 KB | Output is correct |
41 | Correct | 103 ms | 4452 KB | Output is correct |
42 | Correct | 106 ms | 4580 KB | Output is correct |
43 | Correct | 121 ms | 4456 KB | Output is correct |
44 | Correct | 120 ms | 4452 KB | Output is correct |
45 | Correct | 107 ms | 4968 KB | Output is correct |
46 | Correct | 101 ms | 4196 KB | Output is correct |
47 | Correct | 112 ms | 5092 KB | Output is correct |
48 | Correct | 125 ms | 4996 KB | Output is correct |
49 | Correct | 94 ms | 4656 KB | Output is correct |
50 | Correct | 123 ms | 4580 KB | Output is correct |