#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
map<int,vvl>vals;
int main()
{
int s,n;
cin>>s>>n;
vvl a(n,vl(3));
for (int i = 0;i<n;i++){cin>>a[i][0]>>a[i][1]>>a[i][2];vals[a[i][1]].push_back(a[i]);}
if (n == 1){
int weight = a[0][1],worth = a[0][0],copies = a[0][2];
int num = s / weight;
num = min(num,copies);
cout<<worth * num;
return 0;
}
vvl sack;
for (int w = 1;w<=s;w++){
vvl cur = vals[w];
sort(cur.rbegin(),cur.rend());
int num = s/w;
int i = 0;
while (i<(int)cur.size() && num > 0){
num--;
sack.push_back({cur[i][0],w});
cur[i][2]--;
if (cur[i][2] == 0)i++;
}
}
n = (int)sack.size();
vvl dp(n,vl(s + 1));
for (int i = 0;i<n;i++){
for (int j = 1;j<=s;j++){
if (i != 0)dp[i][j] = dp[i - 1][j];
if (j < sack[i][1])continue;
int extra = (i == 0 ? 0 : dp[i - 1][j - sack[i][1]]);
dp[i][j] = max(dp[i][j],sack[i][0] + extra);
}
}
cout<<dp[n - 1][s];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
1996 KB |
Output is correct |
3 |
Correct |
3 ms |
1960 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
548 KB |
Output is correct |
6 |
Correct |
3 ms |
1996 KB |
Output is correct |
7 |
Correct |
3 ms |
1996 KB |
Output is correct |
8 |
Correct |
3 ms |
1868 KB |
Output is correct |
9 |
Correct |
3 ms |
1956 KB |
Output is correct |
10 |
Correct |
3 ms |
1868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
1996 KB |
Output is correct |
3 |
Correct |
3 ms |
1960 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
548 KB |
Output is correct |
6 |
Correct |
3 ms |
1996 KB |
Output is correct |
7 |
Correct |
3 ms |
1996 KB |
Output is correct |
8 |
Correct |
3 ms |
1868 KB |
Output is correct |
9 |
Correct |
3 ms |
1956 KB |
Output is correct |
10 |
Correct |
3 ms |
1868 KB |
Output is correct |
11 |
Correct |
1 ms |
292 KB |
Output is correct |
12 |
Correct |
22 ms |
15820 KB |
Output is correct |
13 |
Correct |
3 ms |
1996 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
5 ms |
3788 KB |
Output is correct |
17 |
Correct |
3 ms |
1868 KB |
Output is correct |
18 |
Correct |
4 ms |
2512 KB |
Output is correct |
19 |
Correct |
5 ms |
3656 KB |
Output is correct |
20 |
Correct |
5 ms |
3404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
3 ms |
1996 KB |
Output is correct |
7 |
Correct |
3 ms |
1960 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
548 KB |
Output is correct |
10 |
Correct |
3 ms |
1996 KB |
Output is correct |
11 |
Correct |
3 ms |
1996 KB |
Output is correct |
12 |
Correct |
3 ms |
1868 KB |
Output is correct |
13 |
Correct |
3 ms |
1956 KB |
Output is correct |
14 |
Correct |
3 ms |
1868 KB |
Output is correct |
15 |
Correct |
1 ms |
292 KB |
Output is correct |
16 |
Correct |
22 ms |
15820 KB |
Output is correct |
17 |
Correct |
3 ms |
1996 KB |
Output is correct |
18 |
Correct |
1 ms |
460 KB |
Output is correct |
19 |
Correct |
1 ms |
460 KB |
Output is correct |
20 |
Correct |
5 ms |
3788 KB |
Output is correct |
21 |
Correct |
3 ms |
1868 KB |
Output is correct |
22 |
Correct |
4 ms |
2512 KB |
Output is correct |
23 |
Correct |
5 ms |
3656 KB |
Output is correct |
24 |
Correct |
5 ms |
3404 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
44 ms |
31900 KB |
Output is correct |
27 |
Correct |
3 ms |
1996 KB |
Output is correct |
28 |
Correct |
1 ms |
460 KB |
Output is correct |
29 |
Correct |
1 ms |
556 KB |
Output is correct |
30 |
Correct |
15 ms |
10700 KB |
Output is correct |
31 |
Correct |
3 ms |
1996 KB |
Output is correct |
32 |
Correct |
3 ms |
2252 KB |
Output is correct |
33 |
Correct |
5 ms |
3276 KB |
Output is correct |
34 |
Correct |
6 ms |
4432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
3 ms |
1996 KB |
Output is correct |
7 |
Correct |
3 ms |
1960 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
548 KB |
Output is correct |
10 |
Correct |
3 ms |
1996 KB |
Output is correct |
11 |
Correct |
3 ms |
1996 KB |
Output is correct |
12 |
Correct |
3 ms |
1868 KB |
Output is correct |
13 |
Correct |
3 ms |
1956 KB |
Output is correct |
14 |
Correct |
3 ms |
1868 KB |
Output is correct |
15 |
Correct |
1 ms |
292 KB |
Output is correct |
16 |
Correct |
22 ms |
15820 KB |
Output is correct |
17 |
Correct |
3 ms |
1996 KB |
Output is correct |
18 |
Correct |
1 ms |
460 KB |
Output is correct |
19 |
Correct |
1 ms |
460 KB |
Output is correct |
20 |
Correct |
5 ms |
3788 KB |
Output is correct |
21 |
Correct |
3 ms |
1868 KB |
Output is correct |
22 |
Correct |
4 ms |
2512 KB |
Output is correct |
23 |
Correct |
5 ms |
3656 KB |
Output is correct |
24 |
Correct |
5 ms |
3404 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
44 ms |
31900 KB |
Output is correct |
27 |
Correct |
3 ms |
1996 KB |
Output is correct |
28 |
Correct |
1 ms |
460 KB |
Output is correct |
29 |
Correct |
1 ms |
556 KB |
Output is correct |
30 |
Correct |
15 ms |
10700 KB |
Output is correct |
31 |
Correct |
3 ms |
1996 KB |
Output is correct |
32 |
Correct |
3 ms |
2252 KB |
Output is correct |
33 |
Correct |
5 ms |
3276 KB |
Output is correct |
34 |
Correct |
6 ms |
4432 KB |
Output is correct |
35 |
Correct |
108 ms |
17780 KB |
Output is correct |
36 |
Correct |
156 ms |
44236 KB |
Output is correct |
37 |
Correct |
150 ms |
43924 KB |
Output is correct |
38 |
Correct |
115 ms |
13856 KB |
Output is correct |
39 |
Correct |
158 ms |
14632 KB |
Output is correct |
40 |
Correct |
497 ms |
258432 KB |
Output is correct |
41 |
Correct |
304 ms |
155860 KB |
Output is correct |
42 |
Correct |
325 ms |
166528 KB |
Output is correct |
43 |
Correct |
447 ms |
258000 KB |
Output is correct |
44 |
Correct |
461 ms |
256896 KB |
Output is correct |
45 |
Correct |
165 ms |
31372 KB |
Output is correct |
46 |
Correct |
142 ms |
18632 KB |
Output is correct |
47 |
Correct |
194 ms |
53316 KB |
Output is correct |
48 |
Correct |
290 ms |
125484 KB |
Output is correct |
49 |
Correct |
136 ms |
15432 KB |
Output is correct |
50 |
Correct |
329 ms |
154804 KB |
Output is correct |