#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
for (; l != r; ++l)
cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x);
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0);
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif
const int N = 200000;
struct item {
int c, f, v, ty;
bool operator < (const item &o) {
if (f == o.f)
return ty < o.ty;
return f > o.f;
}
};
int main () {
owo;
int n, m;
vector <item> a;
cin >> n;
for (int i = 0, c, f, v; i < n; ++i)
cin >> c >> f >> v, a.pb({c, f, v, 0});
cin >> m;
for (int i = 0, c, f, v; i < m; ++i)
cin >> c >> f >> v, a.pb({c, f, v, 1});
sort(all(a));
int S = n * 50 + 1;
vector <lli> dp(S, -1ll << 60);
dp[0] = 0;
for (int i = 0; i < n + m; ++i) {
if (a[i].ty) {
for (int j = 0; j < S - a[i].c; ++j) {
dp[j] = max(dp[j], dp[j + a[i].c] + a[i].v);
}
} else {
for (int j = S - a[i].c - 1; ~j; --j) {
dp[j + a[i].c] = max(dp[j + a[i].c], dp[j] - a[i].v);
}
}
}
cout << *max_element(all(dp)) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
320 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
35 ms |
716 KB |
Output is correct |
6 |
Correct |
45 ms |
716 KB |
Output is correct |
7 |
Correct |
181 ms |
1200 KB |
Output is correct |
8 |
Correct |
165 ms |
1100 KB |
Output is correct |
9 |
Correct |
163 ms |
1196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
4 ms |
332 KB |
Output is correct |
6 |
Correct |
4 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
312 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
109 ms |
948 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
301 ms |
1228 KB |
Output is correct |
6 |
Correct |
380 ms |
1228 KB |
Output is correct |
7 |
Correct |
328 ms |
1228 KB |
Output is correct |
8 |
Correct |
325 ms |
1196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
26 ms |
460 KB |
Output is correct |
4 |
Correct |
69 ms |
712 KB |
Output is correct |
5 |
Correct |
326 ms |
1228 KB |
Output is correct |
6 |
Correct |
360 ms |
1248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
320 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
3 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
304 KB |
Output is correct |
13 |
Correct |
35 ms |
716 KB |
Output is correct |
14 |
Correct |
45 ms |
716 KB |
Output is correct |
15 |
Correct |
181 ms |
1200 KB |
Output is correct |
16 |
Correct |
165 ms |
1100 KB |
Output is correct |
17 |
Correct |
163 ms |
1196 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
4 ms |
332 KB |
Output is correct |
23 |
Correct |
4 ms |
332 KB |
Output is correct |
24 |
Correct |
6 ms |
312 KB |
Output is correct |
25 |
Correct |
6 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
0 ms |
204 KB |
Output is correct |
28 |
Correct |
109 ms |
948 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
301 ms |
1228 KB |
Output is correct |
31 |
Correct |
380 ms |
1228 KB |
Output is correct |
32 |
Correct |
328 ms |
1228 KB |
Output is correct |
33 |
Correct |
325 ms |
1196 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
26 ms |
460 KB |
Output is correct |
37 |
Correct |
69 ms |
712 KB |
Output is correct |
38 |
Correct |
326 ms |
1228 KB |
Output is correct |
39 |
Correct |
360 ms |
1248 KB |
Output is correct |
40 |
Correct |
22 ms |
572 KB |
Output is correct |
41 |
Correct |
66 ms |
684 KB |
Output is correct |
42 |
Correct |
252 ms |
1064 KB |
Output is correct |
43 |
Correct |
331 ms |
1272 KB |
Output is correct |
44 |
Correct |
414 ms |
1228 KB |
Output is correct |
45 |
Correct |
349 ms |
1312 KB |
Output is correct |
46 |
Correct |
106 ms |
716 KB |
Output is correct |
47 |
Correct |
187 ms |
1028 KB |
Output is correct |
48 |
Correct |
196 ms |
1060 KB |
Output is correct |