#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
ll S, N;
cin >> S >> N;
vector<ll> vs(N + 1, 0);
vector<ll> ws(N + 1, 0);
vector<ll> ks(N + 1, 0);
for(int i = 1; i <= N; i++){
ll V;
ll W;
ll K;
cin >> V >> W >> K;
vs[i] = V;
ws[i] = W;
ks[i] = K;
}
vector<vector<ll>> dp(S + 1, vector<ll>(N + 1, 0));
for(int s = 1; s <= S; s++){
for(int i = 1; i <= N; i++){
for(int k = 1; k <= ks[i]; k++){
if(s >= (k * ws[i])){
dp[s][i] = max(dp[s][i], dp[s-(ws[i]*k)][i-1] + (vs[i]*k)) ;
}else{
break;
}
}
dp[s][i] = max(dp[s][i], dp[s][i-1]);
}
}
cout << dp[S][N];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1960 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
1 ms |
1884 KB |
Output is correct |
6 |
Correct |
2 ms |
1884 KB |
Output is correct |
7 |
Correct |
2 ms |
1880 KB |
Output is correct |
8 |
Correct |
2 ms |
1884 KB |
Output is correct |
9 |
Correct |
2 ms |
1884 KB |
Output is correct |
10 |
Correct |
2 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1960 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
1 ms |
1884 KB |
Output is correct |
6 |
Correct |
2 ms |
1884 KB |
Output is correct |
7 |
Correct |
2 ms |
1880 KB |
Output is correct |
8 |
Correct |
2 ms |
1884 KB |
Output is correct |
9 |
Correct |
2 ms |
1884 KB |
Output is correct |
10 |
Correct |
2 ms |
1884 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
4 ms |
1884 KB |
Output is correct |
13 |
Correct |
1 ms |
1884 KB |
Output is correct |
14 |
Correct |
1 ms |
2140 KB |
Output is correct |
15 |
Correct |
2 ms |
1884 KB |
Output is correct |
16 |
Correct |
2 ms |
1884 KB |
Output is correct |
17 |
Correct |
1 ms |
1884 KB |
Output is correct |
18 |
Correct |
2 ms |
1896 KB |
Output is correct |
19 |
Correct |
2 ms |
1944 KB |
Output is correct |
20 |
Correct |
2 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1960 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
2 ms |
1884 KB |
Output is correct |
11 |
Correct |
2 ms |
1880 KB |
Output is correct |
12 |
Correct |
2 ms |
1884 KB |
Output is correct |
13 |
Correct |
2 ms |
1884 KB |
Output is correct |
14 |
Correct |
2 ms |
1884 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
1884 KB |
Output is correct |
17 |
Correct |
1 ms |
1884 KB |
Output is correct |
18 |
Correct |
1 ms |
2140 KB |
Output is correct |
19 |
Correct |
2 ms |
1884 KB |
Output is correct |
20 |
Correct |
2 ms |
1884 KB |
Output is correct |
21 |
Correct |
1 ms |
1884 KB |
Output is correct |
22 |
Correct |
2 ms |
1896 KB |
Output is correct |
23 |
Correct |
2 ms |
1944 KB |
Output is correct |
24 |
Correct |
2 ms |
1884 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
246 ms |
1884 KB |
Output is correct |
27 |
Correct |
1 ms |
1884 KB |
Output is correct |
28 |
Correct |
1 ms |
1884 KB |
Output is correct |
29 |
Correct |
1 ms |
1884 KB |
Output is correct |
30 |
Correct |
3 ms |
1884 KB |
Output is correct |
31 |
Correct |
2 ms |
2080 KB |
Output is correct |
32 |
Correct |
2 ms |
1880 KB |
Output is correct |
33 |
Correct |
2 ms |
1884 KB |
Output is correct |
34 |
Correct |
2 ms |
2012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1960 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
2 ms |
1884 KB |
Output is correct |
11 |
Correct |
2 ms |
1880 KB |
Output is correct |
12 |
Correct |
2 ms |
1884 KB |
Output is correct |
13 |
Correct |
2 ms |
1884 KB |
Output is correct |
14 |
Correct |
2 ms |
1884 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
1884 KB |
Output is correct |
17 |
Correct |
1 ms |
1884 KB |
Output is correct |
18 |
Correct |
1 ms |
2140 KB |
Output is correct |
19 |
Correct |
2 ms |
1884 KB |
Output is correct |
20 |
Correct |
2 ms |
1884 KB |
Output is correct |
21 |
Correct |
1 ms |
1884 KB |
Output is correct |
22 |
Correct |
2 ms |
1896 KB |
Output is correct |
23 |
Correct |
2 ms |
1944 KB |
Output is correct |
24 |
Correct |
2 ms |
1884 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
246 ms |
1884 KB |
Output is correct |
27 |
Correct |
1 ms |
1884 KB |
Output is correct |
28 |
Correct |
1 ms |
1884 KB |
Output is correct |
29 |
Correct |
1 ms |
1884 KB |
Output is correct |
30 |
Correct |
3 ms |
1884 KB |
Output is correct |
31 |
Correct |
2 ms |
2080 KB |
Output is correct |
32 |
Correct |
2 ms |
1880 KB |
Output is correct |
33 |
Correct |
2 ms |
1884 KB |
Output is correct |
34 |
Correct |
2 ms |
2012 KB |
Output is correct |
35 |
Correct |
49 ms |
4948 KB |
Output is correct |
36 |
Runtime error |
140 ms |
262144 KB |
Execution killed with signal 9 |
37 |
Halted |
0 ms |
0 KB |
- |