#include <bits/stdc++.h>
using namespace std;
#define file ""
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
template<class X, class Y> bool mini(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int n, W;
vector<pair<int, int> > adj[N];
int f[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> W >> n;
for (int i = 1; i <= n; ++i) {
int c, e, l;
cin >> c >> e >> l;
// adj[c].emplace_back(e, l);
adj[e].emplace_back(c, l);
}
for (int i = 1; i <= W; ++i) {
sort(all(adj[i]));
reverse(all(adj[i]));
int curW = i;
for (auto [e, l] : adj[i]) {
if (curW > W) break;
for (int j = 0; j < l && curW <= W; ++j, curW += i) {
for (int k = W; k >= i; --k) {
f[k] = max(f[k], f[k - i] + e);
}
}
}
}
cout << f[W];
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25432 KB |
Output is correct |
2 |
Correct |
5 ms |
25436 KB |
Output is correct |
3 |
Correct |
5 ms |
25432 KB |
Output is correct |
4 |
Correct |
5 ms |
25436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25640 KB |
Output is correct |
2 |
Correct |
7 ms |
25436 KB |
Output is correct |
3 |
Correct |
7 ms |
25628 KB |
Output is correct |
4 |
Correct |
5 ms |
25436 KB |
Output is correct |
5 |
Correct |
6 ms |
25568 KB |
Output is correct |
6 |
Correct |
5 ms |
25436 KB |
Output is correct |
7 |
Correct |
6 ms |
25632 KB |
Output is correct |
8 |
Correct |
5 ms |
25436 KB |
Output is correct |
9 |
Correct |
5 ms |
25436 KB |
Output is correct |
10 |
Correct |
6 ms |
25436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25640 KB |
Output is correct |
2 |
Correct |
7 ms |
25436 KB |
Output is correct |
3 |
Correct |
7 ms |
25628 KB |
Output is correct |
4 |
Correct |
5 ms |
25436 KB |
Output is correct |
5 |
Correct |
6 ms |
25568 KB |
Output is correct |
6 |
Correct |
5 ms |
25436 KB |
Output is correct |
7 |
Correct |
6 ms |
25632 KB |
Output is correct |
8 |
Correct |
5 ms |
25436 KB |
Output is correct |
9 |
Correct |
5 ms |
25436 KB |
Output is correct |
10 |
Correct |
6 ms |
25436 KB |
Output is correct |
11 |
Correct |
5 ms |
25432 KB |
Output is correct |
12 |
Correct |
8 ms |
25436 KB |
Output is correct |
13 |
Correct |
6 ms |
25436 KB |
Output is correct |
14 |
Correct |
6 ms |
25436 KB |
Output is correct |
15 |
Correct |
6 ms |
25688 KB |
Output is correct |
16 |
Correct |
5 ms |
25436 KB |
Output is correct |
17 |
Correct |
5 ms |
25436 KB |
Output is correct |
18 |
Correct |
5 ms |
25436 KB |
Output is correct |
19 |
Correct |
5 ms |
25436 KB |
Output is correct |
20 |
Correct |
5 ms |
25436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25432 KB |
Output is correct |
2 |
Correct |
5 ms |
25436 KB |
Output is correct |
3 |
Correct |
5 ms |
25432 KB |
Output is correct |
4 |
Correct |
5 ms |
25436 KB |
Output is correct |
5 |
Correct |
5 ms |
25640 KB |
Output is correct |
6 |
Correct |
7 ms |
25436 KB |
Output is correct |
7 |
Correct |
7 ms |
25628 KB |
Output is correct |
8 |
Correct |
5 ms |
25436 KB |
Output is correct |
9 |
Correct |
6 ms |
25568 KB |
Output is correct |
10 |
Correct |
5 ms |
25436 KB |
Output is correct |
11 |
Correct |
6 ms |
25632 KB |
Output is correct |
12 |
Correct |
5 ms |
25436 KB |
Output is correct |
13 |
Correct |
5 ms |
25436 KB |
Output is correct |
14 |
Correct |
6 ms |
25436 KB |
Output is correct |
15 |
Correct |
5 ms |
25432 KB |
Output is correct |
16 |
Correct |
8 ms |
25436 KB |
Output is correct |
17 |
Correct |
6 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25436 KB |
Output is correct |
19 |
Correct |
6 ms |
25688 KB |
Output is correct |
20 |
Correct |
5 ms |
25436 KB |
Output is correct |
21 |
Correct |
5 ms |
25436 KB |
Output is correct |
22 |
Correct |
5 ms |
25436 KB |
Output is correct |
23 |
Correct |
5 ms |
25436 KB |
Output is correct |
24 |
Correct |
5 ms |
25436 KB |
Output is correct |
25 |
Correct |
5 ms |
25636 KB |
Output is correct |
26 |
Correct |
8 ms |
25436 KB |
Output is correct |
27 |
Correct |
6 ms |
25884 KB |
Output is correct |
28 |
Correct |
5 ms |
25632 KB |
Output is correct |
29 |
Correct |
5 ms |
25436 KB |
Output is correct |
30 |
Correct |
7 ms |
25436 KB |
Output is correct |
31 |
Correct |
5 ms |
25436 KB |
Output is correct |
32 |
Correct |
6 ms |
25544 KB |
Output is correct |
33 |
Correct |
7 ms |
25432 KB |
Output is correct |
34 |
Correct |
5 ms |
25436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25432 KB |
Output is correct |
2 |
Correct |
5 ms |
25436 KB |
Output is correct |
3 |
Correct |
5 ms |
25432 KB |
Output is correct |
4 |
Correct |
5 ms |
25436 KB |
Output is correct |
5 |
Correct |
5 ms |
25640 KB |
Output is correct |
6 |
Correct |
7 ms |
25436 KB |
Output is correct |
7 |
Correct |
7 ms |
25628 KB |
Output is correct |
8 |
Correct |
5 ms |
25436 KB |
Output is correct |
9 |
Correct |
6 ms |
25568 KB |
Output is correct |
10 |
Correct |
5 ms |
25436 KB |
Output is correct |
11 |
Correct |
6 ms |
25632 KB |
Output is correct |
12 |
Correct |
5 ms |
25436 KB |
Output is correct |
13 |
Correct |
5 ms |
25436 KB |
Output is correct |
14 |
Correct |
6 ms |
25436 KB |
Output is correct |
15 |
Correct |
5 ms |
25432 KB |
Output is correct |
16 |
Correct |
8 ms |
25436 KB |
Output is correct |
17 |
Correct |
6 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25436 KB |
Output is correct |
19 |
Correct |
6 ms |
25688 KB |
Output is correct |
20 |
Correct |
5 ms |
25436 KB |
Output is correct |
21 |
Correct |
5 ms |
25436 KB |
Output is correct |
22 |
Correct |
5 ms |
25436 KB |
Output is correct |
23 |
Correct |
5 ms |
25436 KB |
Output is correct |
24 |
Correct |
5 ms |
25436 KB |
Output is correct |
25 |
Correct |
5 ms |
25636 KB |
Output is correct |
26 |
Correct |
8 ms |
25436 KB |
Output is correct |
27 |
Correct |
6 ms |
25884 KB |
Output is correct |
28 |
Correct |
5 ms |
25632 KB |
Output is correct |
29 |
Correct |
5 ms |
25436 KB |
Output is correct |
30 |
Correct |
7 ms |
25436 KB |
Output is correct |
31 |
Correct |
5 ms |
25436 KB |
Output is correct |
32 |
Correct |
6 ms |
25544 KB |
Output is correct |
33 |
Correct |
7 ms |
25432 KB |
Output is correct |
34 |
Correct |
5 ms |
25436 KB |
Output is correct |
35 |
Correct |
28 ms |
27612 KB |
Output is correct |
36 |
Correct |
39 ms |
27864 KB |
Output is correct |
37 |
Correct |
30 ms |
27636 KB |
Output is correct |
38 |
Correct |
28 ms |
27892 KB |
Output is correct |
39 |
Correct |
32 ms |
28532 KB |
Output is correct |
40 |
Correct |
50 ms |
28772 KB |
Output is correct |
41 |
Correct |
36 ms |
28128 KB |
Output is correct |
42 |
Correct |
37 ms |
27992 KB |
Output is correct |
43 |
Correct |
47 ms |
27900 KB |
Output is correct |
44 |
Correct |
50 ms |
27996 KB |
Output is correct |
45 |
Correct |
31 ms |
28756 KB |
Output is correct |
46 |
Correct |
31 ms |
28368 KB |
Output is correct |
47 |
Correct |
39 ms |
28952 KB |
Output is correct |
48 |
Correct |
39 ms |
28752 KB |
Output is correct |
49 |
Correct |
30 ms |
28508 KB |
Output is correct |
50 |
Correct |
43 ms |
28508 KB |
Output is correct |