#include<bits/stdc++.h>
// #define int long long
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define sz size
#define ll long long int
#define pi pair <int,int>
#define itn int
#define fr first
#define sc second
#define srt(v) sort(v.begin(), v.end())
#define rvs(v) reverse(v.begin(), v.end())
#define mod 1000000007
#define INF 1e6
#define N 100010
using namespace std;
itn n, s;
int v[N], ps[N], qtd[N];
map <pair <int, pi>, int> dp;
int solve(int pos, int peso, int quant){
if(peso < 0 or quant < 0) return -INF;
if(pos == 0) return 0;
// if(quant == 0) return solve(pos-1, peso, qtd[pos-1]);
if(dp.find({pos, {peso, quant}}) != dp.end()) return dp[{pos, {peso, quant}}];
// cout << pos << " " << peso << " " << quant << "\n";
dp[{pos, {peso, quant}}] = max(solve(pos-1, peso, qtd[pos-1]), solve(pos, peso - ps[pos], quant - 1) + v[pos]);
return dp[{pos, {peso, quant}}];
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> s >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> ps[i] >> qtd[i];
if(qtd[i] > s/ps[i]){
qtd[i] = s/ps[i];
}
}
solve(n, s, qtd[n]);
// for(int i = 1;i <= n;i++){
// for(int j = 0;j <= s;j++){
// cout << dp[{i, {j, qtd[i]}}] << " ";
// }
// cout << "\n";
// }
cout << dp[{n, {s, qtd[n]}}] << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
4 ms |
852 KB |
Output is correct |
3 |
Correct |
4 ms |
928 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
97 ms |
9812 KB |
Output is correct |
7 |
Correct |
104 ms |
11088 KB |
Output is correct |
8 |
Correct |
65 ms |
7884 KB |
Output is correct |
9 |
Correct |
77 ms |
8332 KB |
Output is correct |
10 |
Correct |
130 ms |
12912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
4 ms |
852 KB |
Output is correct |
3 |
Correct |
4 ms |
928 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
97 ms |
9812 KB |
Output is correct |
7 |
Correct |
104 ms |
11088 KB |
Output is correct |
8 |
Correct |
65 ms |
7884 KB |
Output is correct |
9 |
Correct |
77 ms |
8332 KB |
Output is correct |
10 |
Correct |
130 ms |
12912 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
279 ms |
32932 KB |
Output is correct |
13 |
Correct |
4 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
299 ms |
19968 KB |
Output is correct |
17 |
Correct |
74 ms |
8352 KB |
Output is correct |
18 |
Correct |
115 ms |
11896 KB |
Output is correct |
19 |
Correct |
262 ms |
21680 KB |
Output is correct |
20 |
Correct |
162 ms |
15052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
4 ms |
928 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
97 ms |
9812 KB |
Output is correct |
11 |
Correct |
104 ms |
11088 KB |
Output is correct |
12 |
Correct |
65 ms |
7884 KB |
Output is correct |
13 |
Correct |
77 ms |
8332 KB |
Output is correct |
14 |
Correct |
130 ms |
12912 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
279 ms |
32932 KB |
Output is correct |
17 |
Correct |
4 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
299 ms |
19968 KB |
Output is correct |
21 |
Correct |
74 ms |
8352 KB |
Output is correct |
22 |
Correct |
115 ms |
11896 KB |
Output is correct |
23 |
Correct |
262 ms |
21680 KB |
Output is correct |
24 |
Correct |
162 ms |
15052 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Execution timed out |
1085 ms |
66564 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
4 ms |
928 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
97 ms |
9812 KB |
Output is correct |
11 |
Correct |
104 ms |
11088 KB |
Output is correct |
12 |
Correct |
65 ms |
7884 KB |
Output is correct |
13 |
Correct |
77 ms |
8332 KB |
Output is correct |
14 |
Correct |
130 ms |
12912 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
279 ms |
32932 KB |
Output is correct |
17 |
Correct |
4 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
299 ms |
19968 KB |
Output is correct |
21 |
Correct |
74 ms |
8352 KB |
Output is correct |
22 |
Correct |
115 ms |
11896 KB |
Output is correct |
23 |
Correct |
262 ms |
21680 KB |
Output is correct |
24 |
Correct |
162 ms |
15052 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Execution timed out |
1085 ms |
66564 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |