//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_tuple
#define f first
#define s second
#define turbo(){ \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
}
#define FIO(){ \
freopen("feast.in", "r", stdin); \
freopen("feast.out", "w", stdout);\
}
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<PII, null_type,less<PII>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> PII;
const ll mod = 1e9+7;
const ll inf = 1e18;
const ll inf2 = 1e9;
vector<int> v[2005], num[2005];
map<int, map<int, int>> mp;
int tra[2005][2005];
ll dp[2005];
int main()
{
turbo();
//FIO()
int t = 1;
//cin >> t;
while(t--){
int s, n, i, j, w, va, k;
ll ans = 0;
v[2].pb(1);
cin >> s >> n;
for(i = 0; i < n; i++){
cin >> va >> w >> k;
v[w].pb(va);
mp[w][va] = k;
}
for(i = 1; i <= s; i++){
sort(v[i].rbegin(), v[i].rend());
for(j = 0; j < v[i].size(); j++){
int l = 0;
while(l < mp[i][v[i][j]] && num[i].size() <= 2000){
num[i].pb(v[i][j]);
l++;
}
}
}
for(i = 1; i <= s; i++){
ll mx = 0, up1 = -1, up2 = -1;
for(j = 1; j <= s; j++){
if(i - j >= 0 && tra[i - j][j] < num[j].size()){
if(dp[i - j] + num[j][tra[i - j][j]] > mx){
mx = dp[i - j] + num[j][tra[i - j][j]];
up1 = i - j;
up2 = j;
}
}
}
if(mx){
for(j = 1; j <= s; j++){
tra[i][j] += tra[up1][j];
}
tra[i][up2]++;
dp[i] = mx;
}
ans = max(dp[i], ans);
}
cout << ans << '\n';
}
return 0;
}
Compilation message
knapsack.cpp: In function 'int main()':
knapsack.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(j = 0; j < v[i].size(); j++){
| ~~^~~~~~~~~~~~~
knapsack.cpp:70:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(i - j >= 0 && tra[i - j][j] < num[j].size()){
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9044 KB |
Output is correct |
2 |
Correct |
4 ms |
2260 KB |
Output is correct |
3 |
Correct |
8 ms |
9988 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
21 ms |
16016 KB |
Output is correct |
3 |
Correct |
22 ms |
15952 KB |
Output is correct |
4 |
Correct |
11 ms |
468 KB |
Output is correct |
5 |
Correct |
10 ms |
420 KB |
Output is correct |
6 |
Correct |
25 ms |
15792 KB |
Output is correct |
7 |
Correct |
23 ms |
15920 KB |
Output is correct |
8 |
Correct |
24 ms |
15956 KB |
Output is correct |
9 |
Correct |
24 ms |
15868 KB |
Output is correct |
10 |
Correct |
25 ms |
15940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
21 ms |
16016 KB |
Output is correct |
3 |
Correct |
22 ms |
15952 KB |
Output is correct |
4 |
Correct |
11 ms |
468 KB |
Output is correct |
5 |
Correct |
10 ms |
420 KB |
Output is correct |
6 |
Correct |
25 ms |
15792 KB |
Output is correct |
7 |
Correct |
23 ms |
15920 KB |
Output is correct |
8 |
Correct |
24 ms |
15956 KB |
Output is correct |
9 |
Correct |
24 ms |
15868 KB |
Output is correct |
10 |
Correct |
25 ms |
15940 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
23 ms |
16084 KB |
Output is correct |
13 |
Correct |
26 ms |
16028 KB |
Output is correct |
14 |
Correct |
12 ms |
444 KB |
Output is correct |
15 |
Correct |
10 ms |
412 KB |
Output is correct |
16 |
Correct |
28 ms |
16024 KB |
Output is correct |
17 |
Correct |
23 ms |
15988 KB |
Output is correct |
18 |
Correct |
24 ms |
15792 KB |
Output is correct |
19 |
Correct |
23 ms |
15988 KB |
Output is correct |
20 |
Correct |
26 ms |
15944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9044 KB |
Output is correct |
2 |
Correct |
4 ms |
2260 KB |
Output is correct |
3 |
Correct |
8 ms |
9988 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
21 ms |
16016 KB |
Output is correct |
7 |
Correct |
22 ms |
15952 KB |
Output is correct |
8 |
Correct |
11 ms |
468 KB |
Output is correct |
9 |
Correct |
10 ms |
420 KB |
Output is correct |
10 |
Correct |
25 ms |
15792 KB |
Output is correct |
11 |
Correct |
23 ms |
15920 KB |
Output is correct |
12 |
Correct |
24 ms |
15956 KB |
Output is correct |
13 |
Correct |
24 ms |
15868 KB |
Output is correct |
14 |
Correct |
25 ms |
15940 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
23 ms |
16084 KB |
Output is correct |
17 |
Correct |
26 ms |
16028 KB |
Output is correct |
18 |
Correct |
12 ms |
444 KB |
Output is correct |
19 |
Correct |
10 ms |
412 KB |
Output is correct |
20 |
Correct |
28 ms |
16024 KB |
Output is correct |
21 |
Correct |
23 ms |
15988 KB |
Output is correct |
22 |
Correct |
24 ms |
15792 KB |
Output is correct |
23 |
Correct |
23 ms |
15988 KB |
Output is correct |
24 |
Correct |
26 ms |
15944 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
22 ms |
16088 KB |
Output is correct |
27 |
Correct |
25 ms |
15988 KB |
Output is correct |
28 |
Correct |
11 ms |
424 KB |
Output is correct |
29 |
Correct |
10 ms |
468 KB |
Output is correct |
30 |
Correct |
27 ms |
16848 KB |
Output is correct |
31 |
Correct |
22 ms |
16020 KB |
Output is correct |
32 |
Correct |
25 ms |
15568 KB |
Output is correct |
33 |
Correct |
23 ms |
15996 KB |
Output is correct |
34 |
Correct |
23 ms |
15920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9044 KB |
Output is correct |
2 |
Correct |
4 ms |
2260 KB |
Output is correct |
3 |
Correct |
8 ms |
9988 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
21 ms |
16016 KB |
Output is correct |
7 |
Correct |
22 ms |
15952 KB |
Output is correct |
8 |
Correct |
11 ms |
468 KB |
Output is correct |
9 |
Correct |
10 ms |
420 KB |
Output is correct |
10 |
Correct |
25 ms |
15792 KB |
Output is correct |
11 |
Correct |
23 ms |
15920 KB |
Output is correct |
12 |
Correct |
24 ms |
15956 KB |
Output is correct |
13 |
Correct |
24 ms |
15868 KB |
Output is correct |
14 |
Correct |
25 ms |
15940 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
23 ms |
16084 KB |
Output is correct |
17 |
Correct |
26 ms |
16028 KB |
Output is correct |
18 |
Correct |
12 ms |
444 KB |
Output is correct |
19 |
Correct |
10 ms |
412 KB |
Output is correct |
20 |
Correct |
28 ms |
16024 KB |
Output is correct |
21 |
Correct |
23 ms |
15988 KB |
Output is correct |
22 |
Correct |
24 ms |
15792 KB |
Output is correct |
23 |
Correct |
23 ms |
15988 KB |
Output is correct |
24 |
Correct |
26 ms |
15944 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
22 ms |
16088 KB |
Output is correct |
27 |
Correct |
25 ms |
15988 KB |
Output is correct |
28 |
Correct |
11 ms |
424 KB |
Output is correct |
29 |
Correct |
10 ms |
468 KB |
Output is correct |
30 |
Correct |
27 ms |
16848 KB |
Output is correct |
31 |
Correct |
22 ms |
16020 KB |
Output is correct |
32 |
Correct |
25 ms |
15568 KB |
Output is correct |
33 |
Correct |
23 ms |
15996 KB |
Output is correct |
34 |
Correct |
23 ms |
15920 KB |
Output is correct |
35 |
Correct |
64 ms |
6356 KB |
Output is correct |
36 |
Correct |
100 ms |
22292 KB |
Output is correct |
37 |
Correct |
106 ms |
22044 KB |
Output is correct |
38 |
Correct |
75 ms |
6828 KB |
Output is correct |
39 |
Correct |
93 ms |
7672 KB |
Output is correct |
40 |
Correct |
238 ms |
39712 KB |
Output is correct |
41 |
Correct |
104 ms |
23376 KB |
Output is correct |
42 |
Correct |
105 ms |
23888 KB |
Output is correct |
43 |
Correct |
104 ms |
24100 KB |
Output is correct |
44 |
Correct |
116 ms |
24620 KB |
Output is correct |
45 |
Correct |
112 ms |
25044 KB |
Output is correct |
46 |
Correct |
48 ms |
14668 KB |
Output is correct |
47 |
Correct |
139 ms |
26720 KB |
Output is correct |
48 |
Correct |
173 ms |
31796 KB |
Output is correct |
49 |
Correct |
51 ms |
14924 KB |
Output is correct |
50 |
Correct |
98 ms |
23552 KB |
Output is correct |