#include <bits/stdc++.h>
using namespace std;
#define file "MARKET"
#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);
cin >> W >> n;
for (int i = 1; i <= n; ++i) {
int c, e, l;
cin >> e >> c >> l;
adj[c].emplace_back(e, l);
}
for (int i = 1; i <= W; ++i) {
sort(all(adj[i]));
reverse(all(adj[i]));
int curW = i;
for (auto it : adj[i]) {
int e = it.fi, l = it.se;
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 |
25436 KB |
Output is correct |
2 |
Correct |
5 ms |
25436 KB |
Output is correct |
3 |
Correct |
5 ms |
25436 KB |
Output is correct |
4 |
Correct |
5 ms |
25432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25436 KB |
Output is correct |
2 |
Correct |
6 ms |
25644 KB |
Output is correct |
3 |
Correct |
5 ms |
25436 KB |
Output is correct |
4 |
Correct |
5 ms |
25640 KB |
Output is correct |
5 |
Correct |
5 ms |
25564 KB |
Output is correct |
6 |
Correct |
6 ms |
25688 KB |
Output is correct |
7 |
Correct |
6 ms |
25436 KB |
Output is correct |
8 |
Correct |
6 ms |
25436 KB |
Output is correct |
9 |
Correct |
6 ms |
25688 KB |
Output is correct |
10 |
Correct |
5 ms |
25628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25436 KB |
Output is correct |
2 |
Correct |
6 ms |
25644 KB |
Output is correct |
3 |
Correct |
5 ms |
25436 KB |
Output is correct |
4 |
Correct |
5 ms |
25640 KB |
Output is correct |
5 |
Correct |
5 ms |
25564 KB |
Output is correct |
6 |
Correct |
6 ms |
25688 KB |
Output is correct |
7 |
Correct |
6 ms |
25436 KB |
Output is correct |
8 |
Correct |
6 ms |
25436 KB |
Output is correct |
9 |
Correct |
6 ms |
25688 KB |
Output is correct |
10 |
Correct |
5 ms |
25628 KB |
Output is correct |
11 |
Correct |
5 ms |
25432 KB |
Output is correct |
12 |
Correct |
7 ms |
25648 KB |
Output is correct |
13 |
Correct |
5 ms |
25436 KB |
Output is correct |
14 |
Correct |
6 ms |
25784 KB |
Output is correct |
15 |
Correct |
6 ms |
25504 KB |
Output is correct |
16 |
Correct |
6 ms |
25436 KB |
Output is correct |
17 |
Correct |
5 ms |
25632 KB |
Output is correct |
18 |
Correct |
5 ms |
25436 KB |
Output is correct |
19 |
Correct |
5 ms |
25628 KB |
Output is correct |
20 |
Correct |
5 ms |
25436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25436 KB |
Output is correct |
2 |
Correct |
5 ms |
25436 KB |
Output is correct |
3 |
Correct |
5 ms |
25436 KB |
Output is correct |
4 |
Correct |
5 ms |
25432 KB |
Output is correct |
5 |
Correct |
5 ms |
25436 KB |
Output is correct |
6 |
Correct |
6 ms |
25644 KB |
Output is correct |
7 |
Correct |
5 ms |
25436 KB |
Output is correct |
8 |
Correct |
5 ms |
25640 KB |
Output is correct |
9 |
Correct |
5 ms |
25564 KB |
Output is correct |
10 |
Correct |
6 ms |
25688 KB |
Output is correct |
11 |
Correct |
6 ms |
25436 KB |
Output is correct |
12 |
Correct |
6 ms |
25436 KB |
Output is correct |
13 |
Correct |
6 ms |
25688 KB |
Output is correct |
14 |
Correct |
5 ms |
25628 KB |
Output is correct |
15 |
Correct |
5 ms |
25432 KB |
Output is correct |
16 |
Correct |
7 ms |
25648 KB |
Output is correct |
17 |
Correct |
5 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25784 KB |
Output is correct |
19 |
Correct |
6 ms |
25504 KB |
Output is correct |
20 |
Correct |
6 ms |
25436 KB |
Output is correct |
21 |
Correct |
5 ms |
25632 KB |
Output is correct |
22 |
Correct |
5 ms |
25436 KB |
Output is correct |
23 |
Correct |
5 ms |
25628 KB |
Output is correct |
24 |
Correct |
5 ms |
25436 KB |
Output is correct |
25 |
Correct |
6 ms |
25432 KB |
Output is correct |
26 |
Correct |
8 ms |
25436 KB |
Output is correct |
27 |
Correct |
5 ms |
25436 KB |
Output is correct |
28 |
Correct |
6 ms |
25548 KB |
Output is correct |
29 |
Correct |
5 ms |
25432 KB |
Output is correct |
30 |
Correct |
6 ms |
25944 KB |
Output is correct |
31 |
Correct |
5 ms |
25436 KB |
Output is correct |
32 |
Correct |
5 ms |
25436 KB |
Output is correct |
33 |
Correct |
6 ms |
25436 KB |
Output is correct |
34 |
Correct |
6 ms |
25432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
25436 KB |
Output is correct |
2 |
Correct |
5 ms |
25436 KB |
Output is correct |
3 |
Correct |
5 ms |
25436 KB |
Output is correct |
4 |
Correct |
5 ms |
25432 KB |
Output is correct |
5 |
Correct |
5 ms |
25436 KB |
Output is correct |
6 |
Correct |
6 ms |
25644 KB |
Output is correct |
7 |
Correct |
5 ms |
25436 KB |
Output is correct |
8 |
Correct |
5 ms |
25640 KB |
Output is correct |
9 |
Correct |
5 ms |
25564 KB |
Output is correct |
10 |
Correct |
6 ms |
25688 KB |
Output is correct |
11 |
Correct |
6 ms |
25436 KB |
Output is correct |
12 |
Correct |
6 ms |
25436 KB |
Output is correct |
13 |
Correct |
6 ms |
25688 KB |
Output is correct |
14 |
Correct |
5 ms |
25628 KB |
Output is correct |
15 |
Correct |
5 ms |
25432 KB |
Output is correct |
16 |
Correct |
7 ms |
25648 KB |
Output is correct |
17 |
Correct |
5 ms |
25436 KB |
Output is correct |
18 |
Correct |
6 ms |
25784 KB |
Output is correct |
19 |
Correct |
6 ms |
25504 KB |
Output is correct |
20 |
Correct |
6 ms |
25436 KB |
Output is correct |
21 |
Correct |
5 ms |
25632 KB |
Output is correct |
22 |
Correct |
5 ms |
25436 KB |
Output is correct |
23 |
Correct |
5 ms |
25628 KB |
Output is correct |
24 |
Correct |
5 ms |
25436 KB |
Output is correct |
25 |
Correct |
6 ms |
25432 KB |
Output is correct |
26 |
Correct |
8 ms |
25436 KB |
Output is correct |
27 |
Correct |
5 ms |
25436 KB |
Output is correct |
28 |
Correct |
6 ms |
25548 KB |
Output is correct |
29 |
Correct |
5 ms |
25432 KB |
Output is correct |
30 |
Correct |
6 ms |
25944 KB |
Output is correct |
31 |
Correct |
5 ms |
25436 KB |
Output is correct |
32 |
Correct |
5 ms |
25436 KB |
Output is correct |
33 |
Correct |
6 ms |
25436 KB |
Output is correct |
34 |
Correct |
6 ms |
25432 KB |
Output is correct |
35 |
Correct |
29 ms |
27748 KB |
Output is correct |
36 |
Correct |
31 ms |
27612 KB |
Output is correct |
37 |
Correct |
30 ms |
27652 KB |
Output is correct |
38 |
Correct |
30 ms |
27896 KB |
Output is correct |
39 |
Correct |
31 ms |
28512 KB |
Output is correct |
40 |
Correct |
48 ms |
28740 KB |
Output is correct |
41 |
Correct |
37 ms |
27960 KB |
Output is correct |
42 |
Correct |
37 ms |
28020 KB |
Output is correct |
43 |
Correct |
48 ms |
28016 KB |
Output is correct |
44 |
Correct |
45 ms |
27996 KB |
Output is correct |
45 |
Correct |
32 ms |
28756 KB |
Output is correct |
46 |
Correct |
31 ms |
28364 KB |
Output is correct |
47 |
Correct |
32 ms |
28756 KB |
Output is correct |
48 |
Correct |
38 ms |
28840 KB |
Output is correct |
49 |
Correct |
29 ms |
28620 KB |
Output is correct |
50 |
Correct |
41 ms |
28500 KB |
Output is correct |