# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
488599 | 2021-11-19T18:04:43 Z | A_D | Knapsack (NOI18_knapsack) | C++14 | 131 ms | 146384 KB |
#include <bits/stdc++.h> //#define int long long #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++){ // cout<<a[i].S<<" "<<a[i].F.S<<" "<<szz[i]<<endl; 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]; // cout<<dp[i][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[i][j]<<" "; } // cout<<endl; } cout<<dp[sz][s]<<endl; } main() { // cout<<INT_MAX<<endl; /* int ans=0; for(int i=1;i<=2000;i++){ ans+=2000/i; } cout<<ans<<endl; */ //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 | 296 KB | Output is correct |
3 | Correct | 1 ms | 1320 KB | Output is correct |
4 | Correct | 1 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 | 1 ms | 276 KB | Output is correct |
5 | Correct | 1 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 | 1100 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 | 1 ms | 276 KB | Output is correct |
5 | Correct | 1 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 | 1100 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 6 ms | 8268 KB | Output is correct |
13 | Correct | 1 ms | 1100 KB | Output is correct |
14 | Correct | 1 ms | 296 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 | 1 ms | 1996 KB | Output is correct |
20 | Correct | 1 ms | 1840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 296 KB | Output is correct |
3 | Correct | 1 ms | 1320 KB | Output is correct |
4 | Correct | 1 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 | 1 ms | 276 KB | Output is correct |
9 | Correct | 1 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 | 1100 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 6 ms | 8268 KB | Output is correct |
17 | Correct | 1 ms | 1100 KB | Output is correct |
18 | Correct | 1 ms | 296 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 | 1 ms | 1996 KB | Output is correct |
24 | Correct | 1 ms | 1840 KB | Output is correct |
25 | Correct | 0 ms | 204 KB | Output is correct |
26 | Correct | 12 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 | 1740 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 | 296 KB | Output is correct |
3 | Correct | 1 ms | 1320 KB | Output is correct |
4 | Correct | 1 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 | 1 ms | 276 KB | Output is correct |
9 | Correct | 1 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 | 1100 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 6 ms | 8268 KB | Output is correct |
17 | Correct | 1 ms | 1100 KB | Output is correct |
18 | Correct | 1 ms | 296 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 | 1 ms | 1996 KB | Output is correct |
24 | Correct | 1 ms | 1840 KB | Output is correct |
25 | Correct | 0 ms | 204 KB | Output is correct |
26 | Correct | 12 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 | 1740 KB | Output is correct |
34 | Correct | 2 ms | 2380 KB | Output is correct |
35 | Correct | 29 ms | 1656 KB | Output is correct |
36 | Correct | 43 ms | 17860 KB | Output is correct |
37 | Correct | 40 ms | 17920 KB | Output is correct |
38 | Correct | 30 ms | 1604 KB | Output is correct |
39 | Correct | 35 ms | 1588 KB | Output is correct |
40 | Correct | 126 ms | 146384 KB | Output is correct |
41 | Correct | 90 ms | 92732 KB | Output is correct |
42 | Correct | 90 ms | 98392 KB | Output is correct |
43 | Correct | 131 ms | 146372 KB | Output is correct |
44 | Correct | 127 ms | 146136 KB | Output is correct |
45 | Correct | 45 ms | 12972 KB | Output is correct |
46 | Correct | 34 ms | 2252 KB | Output is correct |
47 | Correct | 52 ms | 25824 KB | Output is correct |
48 | Correct | 81 ms | 68476 KB | Output is correct |
49 | Correct | 35 ms | 3396 KB | Output is correct |
50 | Correct | 87 ms | 76508 KB | Output is correct |