# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
634737 |
2022-08-24T19:00:01 Z |
Wael |
Knapsack (NOI18_knapsack) |
C++14 |
|
127 ms |
42324 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define F first
#define S second
#define endl '\n'
int const M = 2e3 + 10 , mod = 1e9 + 7;
ll n , T , Q , ans , W , val , w , c , dp[M][M] , ben[M][M];
vector<pair<ll , ll>>elem[M];
main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
cin >> W >> n;
for(int i = 1 ; i <= n ; ++i) {
cin >> val >> w >> c;
elem[w].push_back({val , c});
}
for(int w = 1 ; w <= W ; ++w) {
sort(elem[w].begin() , elem[w].end());
int Can = W / w , rem = 0 , val = 0;
for(int cnt = 1 ; cnt <= Can ; ++cnt) {
if(!rem) {
if(!elem[w].size()) break;
rem = elem[w].back().S;
val = elem[w].back().F;
elem[w].pop_back();
//cout << "val " << val << endl;
}
--rem;
ben[w][cnt] = ben[w][cnt - 1] + val;
}
}
for(int w = 1 ; w <= W ; ++w) { //cout << "w = " << w << endl;
int Can = W / w;
for(int cnt = 0 ; cnt <= Can ; ++cnt) {
for(int have = 0 ; have <= W ; ++have) {
dp[w][have] = max(dp[w][have] , dp[w - 1][have]);
if(have - cnt * w < 0) continue;
//cout << " cnt = " << cnt << " " << ben[w][cnt] << endl;
dp[w][have] = max(dp[w][have] , dp[w - 1][have - w * cnt] + ben[w][cnt]);
ans = max(ans , dp[w][have]);
}
}
}
cout << ans << endl;
return 0;
}
Compilation message
knapsack.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
12 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
17228 KB |
Output is correct |
2 |
Correct |
30 ms |
17164 KB |
Output is correct |
3 |
Correct |
31 ms |
17164 KB |
Output is correct |
4 |
Correct |
32 ms |
17272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
69 ms |
31816 KB |
Output is correct |
3 |
Correct |
71 ms |
31820 KB |
Output is correct |
4 |
Correct |
74 ms |
31772 KB |
Output is correct |
5 |
Correct |
70 ms |
31904 KB |
Output is correct |
6 |
Correct |
70 ms |
32252 KB |
Output is correct |
7 |
Correct |
70 ms |
32212 KB |
Output is correct |
8 |
Correct |
75 ms |
32156 KB |
Output is correct |
9 |
Correct |
74 ms |
32204 KB |
Output is correct |
10 |
Correct |
72 ms |
32256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
69 ms |
31816 KB |
Output is correct |
3 |
Correct |
71 ms |
31820 KB |
Output is correct |
4 |
Correct |
74 ms |
31772 KB |
Output is correct |
5 |
Correct |
70 ms |
31904 KB |
Output is correct |
6 |
Correct |
70 ms |
32252 KB |
Output is correct |
7 |
Correct |
70 ms |
32212 KB |
Output is correct |
8 |
Correct |
75 ms |
32156 KB |
Output is correct |
9 |
Correct |
74 ms |
32204 KB |
Output is correct |
10 |
Correct |
72 ms |
32256 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
71 ms |
31840 KB |
Output is correct |
13 |
Correct |
71 ms |
31860 KB |
Output is correct |
14 |
Correct |
72 ms |
31904 KB |
Output is correct |
15 |
Correct |
77 ms |
31820 KB |
Output is correct |
16 |
Correct |
79 ms |
32232 KB |
Output is correct |
17 |
Correct |
70 ms |
32148 KB |
Output is correct |
18 |
Correct |
72 ms |
32156 KB |
Output is correct |
19 |
Correct |
71 ms |
32192 KB |
Output is correct |
20 |
Correct |
77 ms |
32148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
17228 KB |
Output is correct |
2 |
Correct |
30 ms |
17164 KB |
Output is correct |
3 |
Correct |
31 ms |
17164 KB |
Output is correct |
4 |
Correct |
32 ms |
17272 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
69 ms |
31816 KB |
Output is correct |
7 |
Correct |
71 ms |
31820 KB |
Output is correct |
8 |
Correct |
74 ms |
31772 KB |
Output is correct |
9 |
Correct |
70 ms |
31904 KB |
Output is correct |
10 |
Correct |
70 ms |
32252 KB |
Output is correct |
11 |
Correct |
70 ms |
32212 KB |
Output is correct |
12 |
Correct |
75 ms |
32156 KB |
Output is correct |
13 |
Correct |
74 ms |
32204 KB |
Output is correct |
14 |
Correct |
72 ms |
32256 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
71 ms |
31840 KB |
Output is correct |
17 |
Correct |
71 ms |
31860 KB |
Output is correct |
18 |
Correct |
72 ms |
31904 KB |
Output is correct |
19 |
Correct |
77 ms |
31820 KB |
Output is correct |
20 |
Correct |
79 ms |
32232 KB |
Output is correct |
21 |
Correct |
70 ms |
32148 KB |
Output is correct |
22 |
Correct |
72 ms |
32156 KB |
Output is correct |
23 |
Correct |
71 ms |
32192 KB |
Output is correct |
24 |
Correct |
77 ms |
32148 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
72 ms |
31848 KB |
Output is correct |
27 |
Correct |
72 ms |
31796 KB |
Output is correct |
28 |
Correct |
70 ms |
31796 KB |
Output is correct |
29 |
Correct |
73 ms |
31872 KB |
Output is correct |
30 |
Correct |
74 ms |
32204 KB |
Output is correct |
31 |
Correct |
75 ms |
32192 KB |
Output is correct |
32 |
Correct |
73 ms |
32152 KB |
Output is correct |
33 |
Correct |
74 ms |
32224 KB |
Output is correct |
34 |
Correct |
72 ms |
32224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
17228 KB |
Output is correct |
2 |
Correct |
30 ms |
17164 KB |
Output is correct |
3 |
Correct |
31 ms |
17164 KB |
Output is correct |
4 |
Correct |
32 ms |
17272 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
69 ms |
31816 KB |
Output is correct |
7 |
Correct |
71 ms |
31820 KB |
Output is correct |
8 |
Correct |
74 ms |
31772 KB |
Output is correct |
9 |
Correct |
70 ms |
31904 KB |
Output is correct |
10 |
Correct |
70 ms |
32252 KB |
Output is correct |
11 |
Correct |
70 ms |
32212 KB |
Output is correct |
12 |
Correct |
75 ms |
32156 KB |
Output is correct |
13 |
Correct |
74 ms |
32204 KB |
Output is correct |
14 |
Correct |
72 ms |
32256 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
71 ms |
31840 KB |
Output is correct |
17 |
Correct |
71 ms |
31860 KB |
Output is correct |
18 |
Correct |
72 ms |
31904 KB |
Output is correct |
19 |
Correct |
77 ms |
31820 KB |
Output is correct |
20 |
Correct |
79 ms |
32232 KB |
Output is correct |
21 |
Correct |
70 ms |
32148 KB |
Output is correct |
22 |
Correct |
72 ms |
32156 KB |
Output is correct |
23 |
Correct |
71 ms |
32192 KB |
Output is correct |
24 |
Correct |
77 ms |
32148 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
72 ms |
31848 KB |
Output is correct |
27 |
Correct |
72 ms |
31796 KB |
Output is correct |
28 |
Correct |
70 ms |
31796 KB |
Output is correct |
29 |
Correct |
73 ms |
31872 KB |
Output is correct |
30 |
Correct |
74 ms |
32204 KB |
Output is correct |
31 |
Correct |
75 ms |
32192 KB |
Output is correct |
32 |
Correct |
73 ms |
32152 KB |
Output is correct |
33 |
Correct |
74 ms |
32224 KB |
Output is correct |
34 |
Correct |
72 ms |
32224 KB |
Output is correct |
35 |
Correct |
27 ms |
2512 KB |
Output is correct |
36 |
Correct |
97 ms |
33564 KB |
Output is correct |
37 |
Correct |
101 ms |
33564 KB |
Output is correct |
38 |
Correct |
100 ms |
33884 KB |
Output is correct |
39 |
Correct |
106 ms |
33608 KB |
Output is correct |
40 |
Correct |
108 ms |
42180 KB |
Output is correct |
41 |
Correct |
108 ms |
42212 KB |
Output is correct |
42 |
Correct |
98 ms |
42324 KB |
Output is correct |
43 |
Correct |
100 ms |
42244 KB |
Output is correct |
44 |
Correct |
103 ms |
42132 KB |
Output is correct |
45 |
Correct |
103 ms |
35096 KB |
Output is correct |
46 |
Correct |
100 ms |
33584 KB |
Output is correct |
47 |
Correct |
105 ms |
36032 KB |
Output is correct |
48 |
Correct |
103 ms |
38120 KB |
Output is correct |
49 |
Correct |
127 ms |
34308 KB |
Output is correct |
50 |
Correct |
104 ms |
34112 KB |
Output is correct |