# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
887783 | 2023-12-15T08:16:54 Z | conthoanco | Knapsack (NOI18_knapsack) | C++14 | 76 ms | 3156 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define II pair < int , int > #define pb push_back #define mset(a , b) memset(a , b , sizeof a) #define all(a) (a).begin() , (a).end() const int N = 1e5 + 5; int s, n, v[N], w[N], k[N], dp[2][N]; vector<II> lst[2005], vc; void input() { cin >> s >> n; for(int i = 1; i <= n; ++i) { cin >> v[i] >> w[i] >> k[i]; k[i] = min(k[i], s); lst[w[i]].pb({v[i], k[i]}); } } void solve() { vc.pb({0, 0}); for(int i = 1; i <= s; ++i) { sort(lst[i].rbegin(), lst[i].rend()); int lim = s / i; for(auto j: lst[i]) { if(lim == 0) break; int cur = min(lim, j.se); lim -= cur; while(cur--) vc.pb({j.fi, i}); } } int res = 0; for(int i = 1; i < vc.size(); ++i) { for(int curS = 0; curS <= s; ++curS) { dp[i % 2][curS] = dp[1 - i % 2][curS]; if(curS >= vc[i].se) dp[i % 2][curS] = max(dp[i % 2][curS], dp[1 - i % 2][curS - vc[i].se] + vc[i].fi); res = max(res, dp[i % 2][curS]); } } cout << res; } int main() { if(fopen("trash.inp" , "r")) freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout); // else freopen(".inp" , "r" , stdin) , freopen(".out" , "w" , stdout); ios::sync_with_stdio(0); cin.tie(0); input(); solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 600 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 4 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 344 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 4 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 7 ms | 348 KB | Output is correct |
27 | Correct | 1 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 2 ms | 564 KB | Output is correct |
31 | Correct | 1 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 344 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 344 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 4 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 7 ms | 348 KB | Output is correct |
27 | Correct | 1 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 2 ms | 564 KB | Output is correct |
31 | Correct | 1 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 344 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 348 KB | Output is correct |
35 | Correct | 22 ms | 2520 KB | Output is correct |
36 | Correct | 31 ms | 2616 KB | Output is correct |
37 | Correct | 28 ms | 2604 KB | Output is correct |
38 | Correct | 23 ms | 2520 KB | Output is correct |
39 | Correct | 26 ms | 2508 KB | Output is correct |
40 | Correct | 76 ms | 3156 KB | Output is correct |
41 | Correct | 47 ms | 2904 KB | Output is correct |
42 | Correct | 49 ms | 2956 KB | Output is correct |
43 | Correct | 69 ms | 3132 KB | Output is correct |
44 | Correct | 68 ms | 3132 KB | Output is correct |
45 | Correct | 27 ms | 2836 KB | Output is correct |
46 | Correct | 20 ms | 2520 KB | Output is correct |
47 | Correct | 35 ms | 2900 KB | Output is correct |
48 | Correct | 45 ms | 2908 KB | Output is correct |
49 | Correct | 20 ms | 2904 KB | Output is correct |
50 | Correct | 53 ms | 2880 KB | Output is correct |