#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
const ll INF = 1e9; //4e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll LOG = 30; //20;
const double EPS = 1e-9;
#define vi vector <int>
#define vll vector <ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ipi pair <int, pii>
#define lpl pair <ll, pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define apaaja ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll t, n;
vector < vector <pll> > v;
vector <pll> item;
bool mrg (pll a, pll b){
return a.fi > b.fi;
}
int main(){
apaaja
cin >> t >> n;
v.resize(t+1);
for(ll i = 1; i <= n; i++){
ll l, e, k;
cin >> l >> e >> k;
v[e].pb(mp(l, k));
}
item.push_back({0, 0});
for(ll i = 1; i <= t; i++){
sort(v[i].begin(), v[i].end(), mrg);
ll cnt = 0, j = 0;
while(cnt < (t/i) and j < v[i].size()){
item.push_back({v[i][j].first, i});
v[i][j].second--;
cnt++;
if(v[i][j].second == 0) j++;
}
}
// for(auto i : item){
// cout << i.first << ' ' << i.second << '\n';
// }
ll dp [item.size()+1][2005];
memset(dp, 0, sizeof(dp));
for(ll i = 1; i < item.size(); i++){
for(ll j = 1; j <= t; j++){
dp[i][j] = dp[i-1][j];
if(j >= item[i].se){
dp[i][j] = max(dp[i][j], dp[i-1][j-item[i].second] + item[i].fi);
}
// cout << i << " << " << j << " << " << dp[i][j] << endl;
}
}
cout << dp[item.size() - 1][t] << endl;
// vector<ll> dp(t + 1, 0);
// for(ll i = 1; i <= item.size(); i++){
// vector<ll> tmp = dp;
// for(ll j = 1; j <= t; j++){
// if(j >= item[i].se){
// tmp[j] = max(tmp[j], dp[j-item[i].second] + item[i].fi);
// }
// // cout << i << " << " << j << " << " << dp[i][j] << endl;
// dp = tmp;
// for(auto i : dp) cout << i << ' ';
// cout << '\n';
// }
// }
// cout << dp[t] << endl;
}
Compilation message
knapsack.cpp: In function 'int main()':
knapsack.cpp:44:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while(cnt < (t/i) and j < v[i].size()){
| ~~^~~~~~~~~~~~~
knapsack.cpp:58:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(ll i = 1; i < item.size(); i++){
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
2260 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
1856 KB |
Output is correct |
7 |
Correct |
2 ms |
1852 KB |
Output is correct |
8 |
Correct |
1 ms |
1856 KB |
Output is correct |
9 |
Correct |
1 ms |
1856 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
1856 KB |
Output is correct |
7 |
Correct |
2 ms |
1852 KB |
Output is correct |
8 |
Correct |
1 ms |
1856 KB |
Output is correct |
9 |
Correct |
1 ms |
1856 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
9 ms |
15740 KB |
Output is correct |
13 |
Correct |
1 ms |
1876 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
3796 KB |
Output is correct |
17 |
Correct |
1 ms |
1856 KB |
Output is correct |
18 |
Correct |
1 ms |
2260 KB |
Output is correct |
19 |
Correct |
2 ms |
3540 KB |
Output is correct |
20 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
2260 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
1856 KB |
Output is correct |
11 |
Correct |
2 ms |
1852 KB |
Output is correct |
12 |
Correct |
1 ms |
1856 KB |
Output is correct |
13 |
Correct |
1 ms |
1856 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
9 ms |
15740 KB |
Output is correct |
17 |
Correct |
1 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
3796 KB |
Output is correct |
21 |
Correct |
1 ms |
1856 KB |
Output is correct |
22 |
Correct |
1 ms |
2260 KB |
Output is correct |
23 |
Correct |
2 ms |
3540 KB |
Output is correct |
24 |
Correct |
2 ms |
3412 KB |
Output is correct |
25 |
Correct |
1 ms |
320 KB |
Output is correct |
26 |
Correct |
18 ms |
31700 KB |
Output is correct |
27 |
Correct |
1 ms |
1856 KB |
Output is correct |
28 |
Correct |
1 ms |
448 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
6 ms |
10580 KB |
Output is correct |
31 |
Correct |
1 ms |
1876 KB |
Output is correct |
32 |
Correct |
1 ms |
2132 KB |
Output is correct |
33 |
Correct |
2 ms |
3156 KB |
Output is correct |
34 |
Correct |
2 ms |
4436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
2260 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
1856 KB |
Output is correct |
11 |
Correct |
2 ms |
1852 KB |
Output is correct |
12 |
Correct |
1 ms |
1856 KB |
Output is correct |
13 |
Correct |
1 ms |
1856 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
9 ms |
15740 KB |
Output is correct |
17 |
Correct |
1 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
3796 KB |
Output is correct |
21 |
Correct |
1 ms |
1856 KB |
Output is correct |
22 |
Correct |
1 ms |
2260 KB |
Output is correct |
23 |
Correct |
2 ms |
3540 KB |
Output is correct |
24 |
Correct |
2 ms |
3412 KB |
Output is correct |
25 |
Correct |
1 ms |
320 KB |
Output is correct |
26 |
Correct |
18 ms |
31700 KB |
Output is correct |
27 |
Correct |
1 ms |
1856 KB |
Output is correct |
28 |
Correct |
1 ms |
448 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
6 ms |
10580 KB |
Output is correct |
31 |
Correct |
1 ms |
1876 KB |
Output is correct |
32 |
Correct |
1 ms |
2132 KB |
Output is correct |
33 |
Correct |
2 ms |
3156 KB |
Output is correct |
34 |
Correct |
2 ms |
4436 KB |
Output is correct |
35 |
Correct |
24 ms |
3404 KB |
Output is correct |
36 |
Correct |
44 ms |
34704 KB |
Output is correct |
37 |
Correct |
41 ms |
34536 KB |
Output is correct |
38 |
Correct |
24 ms |
3884 KB |
Output is correct |
39 |
Correct |
28 ms |
4324 KB |
Output is correct |
40 |
Correct |
154 ms |
248352 KB |
Output is correct |
41 |
Correct |
95 ms |
145896 KB |
Output is correct |
42 |
Correct |
102 ms |
156488 KB |
Output is correct |
43 |
Correct |
147 ms |
247952 KB |
Output is correct |
44 |
Correct |
143 ms |
247304 KB |
Output is correct |
45 |
Correct |
35 ms |
22108 KB |
Output is correct |
46 |
Correct |
22 ms |
4072 KB |
Output is correct |
47 |
Correct |
46 ms |
43896 KB |
Output is correct |
48 |
Correct |
85 ms |
115908 KB |
Output is correct |
49 |
Correct |
22 ms |
6088 KB |
Output is correct |
50 |
Correct |
97 ms |
145324 KB |
Output is correct |