#include<bits/stdc++.h>
#include <iostream>
typedef long long ll;
#define pb push_back
#define f first
#define s second
using namespace std;
ll dp[2001];
priority_queue<pair<ll,int>> kolejka[2001];
int n,max_weight;
void put(int waga){
auto x=kolejka[waga].top();
kolejka[waga].pop();
ll val=x.f; x.s--;
if(x.s)kolejka[waga].push(x);
if(kolejka[waga].top().s==0)kolejka[waga].pop();
for(int i=max_weight-waga;i>=0;i--)
dp[i+waga]=max(dp[i+waga],dp[i]+val);
for(int i=1;i<=max_weight;i++)dp[i]=max(dp[i],dp[i-1]);
}
int main()
{
cin>>max_weight>>n;
for(int i=0;i<n;i++){
ll v; int w,k;
cin>>v>>w>>k;
kolejka[w].push({v,k});
}
for(int i=1;i<=max_weight;i++){
for(int j=0;j<max_weight/i;j++){
if(kolejka[i].empty())break;
put(i);
}
}
cout<<dp[max_weight];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
360 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
360 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
9 ms |
408 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
360 KB |
Output is correct |
16 |
Correct |
3 ms |
364 KB |
Output is correct |
17 |
Correct |
2 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
340 KB |
Output is correct |
19 |
Correct |
3 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
360 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
9 ms |
408 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
360 KB |
Output is correct |
20 |
Correct |
3 ms |
364 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
3 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
360 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
18 ms |
360 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
6 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
340 KB |
Output is correct |
33 |
Correct |
2 ms |
340 KB |
Output is correct |
34 |
Correct |
3 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
360 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
9 ms |
408 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
360 KB |
Output is correct |
20 |
Correct |
3 ms |
364 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
3 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
360 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
18 ms |
360 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
6 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
340 KB |
Output is correct |
33 |
Correct |
2 ms |
340 KB |
Output is correct |
34 |
Correct |
3 ms |
340 KB |
Output is correct |
35 |
Correct |
63 ms |
3320 KB |
Output is correct |
36 |
Correct |
87 ms |
3556 KB |
Output is correct |
37 |
Correct |
75 ms |
3352 KB |
Output is correct |
38 |
Correct |
72 ms |
3788 KB |
Output is correct |
39 |
Correct |
90 ms |
4300 KB |
Output is correct |
40 |
Correct |
227 ms |
4660 KB |
Output is correct |
41 |
Correct |
148 ms |
3916 KB |
Output is correct |
42 |
Correct |
149 ms |
3980 KB |
Output is correct |
43 |
Correct |
197 ms |
4000 KB |
Output is correct |
44 |
Correct |
198 ms |
3992 KB |
Output is correct |
45 |
Correct |
101 ms |
4656 KB |
Output is correct |
46 |
Correct |
86 ms |
4060 KB |
Output is correct |
47 |
Correct |
111 ms |
4892 KB |
Output is correct |
48 |
Correct |
146 ms |
4680 KB |
Output is correct |
49 |
Correct |
91 ms |
4412 KB |
Output is correct |
50 |
Correct |
161 ms |
4176 KB |
Output is correct |