# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
652329 | 2022-10-22T06:40:22 Z | lam | Knapsack (NOI18_knapsack) | C++14 | 116 ms | 62256 KB |
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 10; typedef pair<int,int> ii; #define ff first #define ss second int s,n; int v[maxn],w[maxn],k[maxn]; vector <ii> a[maxn]; int dp[2010][2010]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>s>>n; for (int i=1; i<=n; i++) { cin>>v[i]>>w[i]>>k[i]; a[w[i]].push_back({v[i],k[i]}); } for (int i=1; i<=s; i++) { sort(a[i].begin(),a[i].end(),greater<ii>()); for (int j=1; j<=s; j++) { dp[i][j]=dp[i-1][j]; if (a[i].empty()) continue; int it,cnt,used,val; it=cnt=val=0; used=a[i][it].ss; while (it<(int)(a[i].size()) && (cnt+1)*i <=j ) { used--; cnt++; val+=a[i][it].ff; dp[i][j]=max(dp[i][j],dp[i-1][j-cnt*i]+val); if (used==0) { it++; if (it<a[i].size()) used=a[i][it].ss; } } } } int ans=0; for (int i=1; i<=s; i++) ans=max(ans,dp[s][i]); cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 40676 KB | Output is correct |
2 | Correct | 22 ms | 40660 KB | Output is correct |
3 | Correct | 22 ms | 40640 KB | Output is correct |
4 | Correct | 22 ms | 40664 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23784 KB | Output is correct |
2 | Correct | 30 ms | 55240 KB | Output is correct |
3 | Correct | 34 ms | 55168 KB | Output is correct |
4 | Correct | 31 ms | 55168 KB | Output is correct |
5 | Correct | 32 ms | 55220 KB | Output is correct |
6 | Correct | 37 ms | 55288 KB | Output is correct |
7 | Correct | 41 ms | 55244 KB | Output is correct |
8 | Correct | 32 ms | 55244 KB | Output is correct |
9 | Correct | 30 ms | 55172 KB | Output is correct |
10 | Correct | 29 ms | 55276 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23784 KB | Output is correct |
2 | Correct | 30 ms | 55240 KB | Output is correct |
3 | Correct | 34 ms | 55168 KB | Output is correct |
4 | Correct | 31 ms | 55168 KB | Output is correct |
5 | Correct | 32 ms | 55220 KB | Output is correct |
6 | Correct | 37 ms | 55288 KB | Output is correct |
7 | Correct | 41 ms | 55244 KB | Output is correct |
8 | Correct | 32 ms | 55244 KB | Output is correct |
9 | Correct | 30 ms | 55172 KB | Output is correct |
10 | Correct | 29 ms | 55276 KB | Output is correct |
11 | Correct | 13 ms | 23764 KB | Output is correct |
12 | Correct | 38 ms | 55176 KB | Output is correct |
13 | Correct | 31 ms | 55216 KB | Output is correct |
14 | Correct | 36 ms | 55284 KB | Output is correct |
15 | Correct | 29 ms | 55200 KB | Output is correct |
16 | Correct | 31 ms | 55244 KB | Output is correct |
17 | Correct | 32 ms | 55344 KB | Output is correct |
18 | Correct | 38 ms | 55156 KB | Output is correct |
19 | Correct | 38 ms | 55196 KB | Output is correct |
20 | Correct | 30 ms | 55244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 40676 KB | Output is correct |
2 | Correct | 22 ms | 40660 KB | Output is correct |
3 | Correct | 22 ms | 40640 KB | Output is correct |
4 | Correct | 22 ms | 40664 KB | Output is correct |
5 | Correct | 13 ms | 23784 KB | Output is correct |
6 | Correct | 30 ms | 55240 KB | Output is correct |
7 | Correct | 34 ms | 55168 KB | Output is correct |
8 | Correct | 31 ms | 55168 KB | Output is correct |
9 | Correct | 32 ms | 55220 KB | Output is correct |
10 | Correct | 37 ms | 55288 KB | Output is correct |
11 | Correct | 41 ms | 55244 KB | Output is correct |
12 | Correct | 32 ms | 55244 KB | Output is correct |
13 | Correct | 30 ms | 55172 KB | Output is correct |
14 | Correct | 29 ms | 55276 KB | Output is correct |
15 | Correct | 13 ms | 23764 KB | Output is correct |
16 | Correct | 38 ms | 55176 KB | Output is correct |
17 | Correct | 31 ms | 55216 KB | Output is correct |
18 | Correct | 36 ms | 55284 KB | Output is correct |
19 | Correct | 29 ms | 55200 KB | Output is correct |
20 | Correct | 31 ms | 55244 KB | Output is correct |
21 | Correct | 32 ms | 55344 KB | Output is correct |
22 | Correct | 38 ms | 55156 KB | Output is correct |
23 | Correct | 38 ms | 55196 KB | Output is correct |
24 | Correct | 30 ms | 55244 KB | Output is correct |
25 | Correct | 13 ms | 23820 KB | Output is correct |
26 | Correct | 34 ms | 55252 KB | Output is correct |
27 | Correct | 33 ms | 55244 KB | Output is correct |
28 | Correct | 33 ms | 55260 KB | Output is correct |
29 | Correct | 41 ms | 55228 KB | Output is correct |
30 | Correct | 34 ms | 55244 KB | Output is correct |
31 | Correct | 40 ms | 55280 KB | Output is correct |
32 | Correct | 31 ms | 55204 KB | Output is correct |
33 | Correct | 30 ms | 55176 KB | Output is correct |
34 | Correct | 31 ms | 55228 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 40676 KB | Output is correct |
2 | Correct | 22 ms | 40660 KB | Output is correct |
3 | Correct | 22 ms | 40640 KB | Output is correct |
4 | Correct | 22 ms | 40664 KB | Output is correct |
5 | Correct | 13 ms | 23784 KB | Output is correct |
6 | Correct | 30 ms | 55240 KB | Output is correct |
7 | Correct | 34 ms | 55168 KB | Output is correct |
8 | Correct | 31 ms | 55168 KB | Output is correct |
9 | Correct | 32 ms | 55220 KB | Output is correct |
10 | Correct | 37 ms | 55288 KB | Output is correct |
11 | Correct | 41 ms | 55244 KB | Output is correct |
12 | Correct | 32 ms | 55244 KB | Output is correct |
13 | Correct | 30 ms | 55172 KB | Output is correct |
14 | Correct | 29 ms | 55276 KB | Output is correct |
15 | Correct | 13 ms | 23764 KB | Output is correct |
16 | Correct | 38 ms | 55176 KB | Output is correct |
17 | Correct | 31 ms | 55216 KB | Output is correct |
18 | Correct | 36 ms | 55284 KB | Output is correct |
19 | Correct | 29 ms | 55200 KB | Output is correct |
20 | Correct | 31 ms | 55244 KB | Output is correct |
21 | Correct | 32 ms | 55344 KB | Output is correct |
22 | Correct | 38 ms | 55156 KB | Output is correct |
23 | Correct | 38 ms | 55196 KB | Output is correct |
24 | Correct | 30 ms | 55244 KB | Output is correct |
25 | Correct | 13 ms | 23820 KB | Output is correct |
26 | Correct | 34 ms | 55252 KB | Output is correct |
27 | Correct | 33 ms | 55244 KB | Output is correct |
28 | Correct | 33 ms | 55260 KB | Output is correct |
29 | Correct | 41 ms | 55228 KB | Output is correct |
30 | Correct | 34 ms | 55244 KB | Output is correct |
31 | Correct | 40 ms | 55280 KB | Output is correct |
32 | Correct | 31 ms | 55204 KB | Output is correct |
33 | Correct | 30 ms | 55176 KB | Output is correct |
34 | Correct | 31 ms | 55228 KB | Output is correct |
35 | Correct | 41 ms | 28876 KB | Output is correct |
36 | Correct | 64 ms | 60620 KB | Output is correct |
37 | Correct | 67 ms | 60308 KB | Output is correct |
38 | Correct | 60 ms | 60952 KB | Output is correct |
39 | Correct | 72 ms | 61432 KB | Output is correct |
40 | Correct | 116 ms | 61956 KB | Output is correct |
41 | Correct | 72 ms | 61132 KB | Output is correct |
42 | Correct | 78 ms | 61132 KB | Output is correct |
43 | Correct | 83 ms | 61172 KB | Output is correct |
44 | Correct | 81 ms | 61184 KB | Output is correct |
45 | Correct | 71 ms | 62160 KB | Output is correct |
46 | Correct | 72 ms | 61184 KB | Output is correct |
47 | Correct | 74 ms | 62256 KB | Output is correct |
48 | Correct | 85 ms | 61964 KB | Output is correct |
49 | Correct | 66 ms | 61760 KB | Output is correct |
50 | Correct | 79 ms | 61388 KB | Output is correct |