# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
488600 | 2021-11-19T18:05:40 Z | A_D | Knapsack (NOI18_knapsack) | C++14 | 125 ms | 145556 KB |
#include <bits/stdc++.h> #define ii pair<int,int> #define F first #define S second using namespace std; const int N=2e3+100; const int NN=2e5+100; const int M=2e4+100; vector<int> vec; vector<int> w; int szz[N]; int sz; pair<ii,int> a[NN]; int dp[M][N]; void solve() { vec.push_back(0); w.push_back(0); int s,n; cin>>s>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i].F.F); scanf("%d",&a[i].F.S); scanf("%d",&a[i].S); } sort(a+1,a+n+1); reverse(a+1,a+n+1); for(int i=1;i<=n;i++){ while(a[i].S&&s>a[i].F.S*szz[a[i].F.S]){ a[i].S--; szz[a[i].F.S]++; vec.push_back(a[i].F.F); w.push_back(a[i].F.S); sz++; if(sz>=M){ return; } } } for(int i=1;i<=sz;i++){ for(int j=1;j<w[i];j++){ dp[i][j]=dp[i-1][j]; } for(int j=w[i];j<=s;j++){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+vec[i]); } } cout<<dp[sz][s]<<endl; } main() { //freopen("face.in","r",stdin); //freopen("face.out","w",stdout); int t=1; // cin>>t; while(t--){ solve(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 1228 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 1100 KB | Output is correct |
3 | Correct | 1 ms | 1100 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 1100 KB | Output is correct |
7 | Correct | 1 ms | 1100 KB | Output is correct |
8 | Correct | 1 ms | 1100 KB | Output is correct |
9 | Correct | 1 ms | 1100 KB | Output is correct |
10 | Correct | 1 ms | 1052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 1100 KB | Output is correct |
3 | Correct | 1 ms | 1100 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 1100 KB | Output is correct |
7 | Correct | 1 ms | 1100 KB | Output is correct |
8 | Correct | 1 ms | 1100 KB | Output is correct |
9 | Correct | 1 ms | 1100 KB | Output is correct |
10 | Correct | 1 ms | 1052 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 5 ms | 8268 KB | Output is correct |
13 | Correct | 1 ms | 1100 KB | Output is correct |
14 | Correct | 0 ms | 332 KB | Output is correct |
15 | Correct | 0 ms | 332 KB | Output is correct |
16 | Correct | 2 ms | 2636 KB | Output is correct |
17 | Correct | 1 ms | 1100 KB | Output is correct |
18 | Correct | 1 ms | 1484 KB | Output is correct |
19 | Correct | 2 ms | 1996 KB | Output is correct |
20 | Correct | 1 ms | 1868 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 1228 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 1100 KB | Output is correct |
7 | Correct | 1 ms | 1100 KB | Output is correct |
8 | Correct | 0 ms | 332 KB | Output is correct |
9 | Correct | 0 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 1100 KB | Output is correct |
11 | Correct | 1 ms | 1100 KB | Output is correct |
12 | Correct | 1 ms | 1100 KB | Output is correct |
13 | Correct | 1 ms | 1100 KB | Output is correct |
14 | Correct | 1 ms | 1052 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 5 ms | 8268 KB | Output is correct |
17 | Correct | 1 ms | 1100 KB | Output is correct |
18 | Correct | 0 ms | 332 KB | Output is correct |
19 | Correct | 0 ms | 332 KB | Output is correct |
20 | Correct | 2 ms | 2636 KB | Output is correct |
21 | Correct | 1 ms | 1100 KB | Output is correct |
22 | Correct | 1 ms | 1484 KB | Output is correct |
23 | Correct | 2 ms | 1996 KB | Output is correct |
24 | Correct | 1 ms | 1868 KB | Output is correct |
25 | Correct | 0 ms | 204 KB | Output is correct |
26 | Correct | 11 ms | 16716 KB | Output is correct |
27 | Correct | 1 ms | 1100 KB | Output is correct |
28 | Correct | 0 ms | 332 KB | Output is correct |
29 | Correct | 0 ms | 332 KB | Output is correct |
30 | Correct | 4 ms | 6348 KB | Output is correct |
31 | Correct | 1 ms | 1100 KB | Output is correct |
32 | Correct | 1 ms | 1356 KB | Output is correct |
33 | Correct | 1 ms | 1744 KB | Output is correct |
34 | Correct | 2 ms | 2380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 1228 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 1100 KB | Output is correct |
7 | Correct | 1 ms | 1100 KB | Output is correct |
8 | Correct | 0 ms | 332 KB | Output is correct |
9 | Correct | 0 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 1100 KB | Output is correct |
11 | Correct | 1 ms | 1100 KB | Output is correct |
12 | Correct | 1 ms | 1100 KB | Output is correct |
13 | Correct | 1 ms | 1100 KB | Output is correct |
14 | Correct | 1 ms | 1052 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 5 ms | 8268 KB | Output is correct |
17 | Correct | 1 ms | 1100 KB | Output is correct |
18 | Correct | 0 ms | 332 KB | Output is correct |
19 | Correct | 0 ms | 332 KB | Output is correct |
20 | Correct | 2 ms | 2636 KB | Output is correct |
21 | Correct | 1 ms | 1100 KB | Output is correct |
22 | Correct | 1 ms | 1484 KB | Output is correct |
23 | Correct | 2 ms | 1996 KB | Output is correct |
24 | Correct | 1 ms | 1868 KB | Output is correct |
25 | Correct | 0 ms | 204 KB | Output is correct |
26 | Correct | 11 ms | 16716 KB | Output is correct |
27 | Correct | 1 ms | 1100 KB | Output is correct |
28 | Correct | 0 ms | 332 KB | Output is correct |
29 | Correct | 0 ms | 332 KB | Output is correct |
30 | Correct | 4 ms | 6348 KB | Output is correct |
31 | Correct | 1 ms | 1100 KB | Output is correct |
32 | Correct | 1 ms | 1356 KB | Output is correct |
33 | Correct | 1 ms | 1744 KB | Output is correct |
34 | Correct | 2 ms | 2380 KB | Output is correct |
35 | Correct | 29 ms | 1404 KB | Output is correct |
36 | Correct | 41 ms | 17892 KB | Output is correct |
37 | Correct | 39 ms | 17840 KB | Output is correct |
38 | Correct | 30 ms | 1552 KB | Output is correct |
39 | Correct | 35 ms | 1476 KB | Output is correct |
40 | Correct | 125 ms | 145456 KB | Output is correct |
41 | Correct | 90 ms | 91836 KB | Output is correct |
42 | Correct | 92 ms | 97552 KB | Output is correct |
43 | Correct | 122 ms | 145556 KB | Output is correct |
44 | Correct | 119 ms | 145328 KB | Output is correct |
45 | Correct | 43 ms | 12120 KB | Output is correct |
46 | Correct | 33 ms | 1464 KB | Output is correct |
47 | Correct | 53 ms | 25120 KB | Output is correct |
48 | Correct | 80 ms | 67772 KB | Output is correct |
49 | Correct | 35 ms | 2548 KB | Output is correct |
50 | Correct | 86 ms | 75708 KB | Output is correct |