#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)
#define pb push_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define vec vector
using namespace std;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
inline void solve () {
int n; cin >> n;
vector <array <ll, 4>> ful;
vector <ll> c (n), f (n), v (n);
for (int i = 0; i < n; ++i) {
cin >> c[i] >> f[i] >> v[i];
ful.pb({f[i], 1, v[i], c[i]});
}
int m; cin >> m;
vector <ll> qc (m), qf (m), qv (m);
for (int i = 0; i < m; ++i) {
cin >> qc[i] >> qf[i] >> qv[i];
ful.pb({qf[i], 0, qv[i], qc[i]});
}
const int MX = 50 * n + 51;
vector <ll> dp (MX, -1e18);
dp[0] = 0;
sort(all(ful));
while (sz(ful)) {
auto [f, type, v, c] = ful.back();
if (type == 1) {
for (int i = MX - 1 - c; i >= 0; --i) {
dp[i + c] = max(dp[i + c], dp[i] - v);
}
}
else {
for (int i = c; i < MX; ++i) {
dp[i - c] = max(dp[i - c], dp[i] + v);
}
}
ful.pop_back();
}
cout << *max_element(all(dp));
}
signed main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
Compilation message
clo.cpp: In function 'void solve()':
clo.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | auto [f, type, v, c] = ful.back();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
37 ms |
860 KB |
Output is correct |
6 |
Correct |
31 ms |
856 KB |
Output is correct |
7 |
Correct |
153 ms |
1368 KB |
Output is correct |
8 |
Correct |
154 ms |
1368 KB |
Output is correct |
9 |
Correct |
146 ms |
1372 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 |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
348 KB |
Output is correct |
6 |
Correct |
4 ms |
832 KB |
Output is correct |
7 |
Correct |
5 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
89 ms |
1112 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
288 ms |
1524 KB |
Output is correct |
6 |
Correct |
314 ms |
1624 KB |
Output is correct |
7 |
Correct |
295 ms |
1372 KB |
Output is correct |
8 |
Correct |
305 ms |
1372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
18 ms |
604 KB |
Output is correct |
4 |
Correct |
59 ms |
856 KB |
Output is correct |
5 |
Correct |
289 ms |
1368 KB |
Output is correct |
6 |
Correct |
299 ms |
1620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
37 ms |
860 KB |
Output is correct |
14 |
Correct |
31 ms |
856 KB |
Output is correct |
15 |
Correct |
153 ms |
1368 KB |
Output is correct |
16 |
Correct |
154 ms |
1368 KB |
Output is correct |
17 |
Correct |
146 ms |
1372 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
3 ms |
348 KB |
Output is correct |
23 |
Correct |
4 ms |
832 KB |
Output is correct |
24 |
Correct |
5 ms |
348 KB |
Output is correct |
25 |
Correct |
5 ms |
588 KB |
Output is correct |
26 |
Correct |
0 ms |
344 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
89 ms |
1112 KB |
Output is correct |
29 |
Correct |
2 ms |
604 KB |
Output is correct |
30 |
Correct |
288 ms |
1524 KB |
Output is correct |
31 |
Correct |
314 ms |
1624 KB |
Output is correct |
32 |
Correct |
295 ms |
1372 KB |
Output is correct |
33 |
Correct |
305 ms |
1372 KB |
Output is correct |
34 |
Correct |
0 ms |
344 KB |
Output is correct |
35 |
Correct |
1 ms |
600 KB |
Output is correct |
36 |
Correct |
18 ms |
604 KB |
Output is correct |
37 |
Correct |
59 ms |
856 KB |
Output is correct |
38 |
Correct |
289 ms |
1368 KB |
Output is correct |
39 |
Correct |
299 ms |
1620 KB |
Output is correct |
40 |
Correct |
19 ms |
604 KB |
Output is correct |
41 |
Correct |
55 ms |
856 KB |
Output is correct |
42 |
Correct |
183 ms |
1304 KB |
Output is correct |
43 |
Correct |
306 ms |
1536 KB |
Output is correct |
44 |
Correct |
297 ms |
1536 KB |
Output is correct |
45 |
Correct |
295 ms |
1536 KB |
Output is correct |
46 |
Correct |
73 ms |
860 KB |
Output is correct |
47 |
Correct |
170 ms |
1116 KB |
Output is correct |
48 |
Correct |
162 ms |
1116 KB |
Output is correct |