// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;
// -------------------- Typedefs -------------------- //
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
// -------------------- Defines -------------------- //
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ft front
#define bk back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
// -------------------- Constants -------------------- //
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);
// -------------------- Functions -------------------- //
void fastio()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
return;
}
void precision(int x)
{
cout.setf(ios::fixed | ios::showpoint);
cout.precision(x);
return;
}
ll gcd(ll a, ll b)
{
while (b) {
a %= b;
swap(a, b);
}
return a;
}
ll lcm(ll a, ll b)
{
return a / gcd(a, b) * b;
}
bool is_prime(ll a)
{
if (a == 1) {
return false;
}
for (ll i = 2; i * i <= a; i++) {
if (a % i == 0) {
return false;
}
}
return true;
}
bool is_square(ll a)
{
ll b = ll(sqrt(a));
return (b * b == a);
}
bool is_cube(ll a)
{
ll b = ll(cbrt(a));
return (b * b * b == a);
}
int digit_sum(ll a)
{
int sum = 0;
while (a) {
sum += int(a % 10);
a /= 10;
}
return sum;
}
ll binpow(ll a, int b)
{
ll ans = 1;
while (b) {
if ((b & 1) == 1) {
ans *= a;
}
b >>= 1;
a *= a;
}
return ans;
}
ll binpow_by_mod(ll a, ll b, ll mod)
{
ll ans = 1;
while (b) {
if ((b & 1) == 1) {
ans *= a;
ans %= mod;
}
b >>= 1;
a *= a;
a %= mod;
}
return ans;
}
ll factorial(int a)
{
ll ans = 1;
for (int i = 2; i <= a; i++) {
ans *= ll(i);
}
return ans;
}
ll factorial_by_mod(int a, ll mod)
{
ll ans = 1;
for (int i = 2; i <= a; i++) {
ans *= ll(i);
ans %= mod;
}
return ans;
}
// -------------------- Solution -------------------- //
struct comp
{
int c, f;
ll v;
};
const int N = 2005, M = 2005, MC = 55;
comp a[N], b[M];
int n, m, mc;
ll dp[2][M][MC][2];
bool cond(const comp& x, const comp& y)
{
return x.f < y.f;
}
void maxu(ll& x, ll y)
{
x = max(x, y);
}
void solve()
{
int i, j;
int k;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> a[i].c >> a[i].f >> a[i].v;
mc = max(mc, a[i].c);
}
cin >> m;
for (i = 1; i <= m; i++) {
cin >> b[i].c >> b[i].f >> b[i].v;
mc = max(mc, b[i].c);
}
sort(a + 1, a + n + 1, cond);
sort(b + 1, b + m + 1, cond);
for (i = 0; i <= 1; i++)
for (j = 0; j <= m + 1; j++)
for (k = 0; k <= mc + 1; k++)
dp[i][j][k][0] = dp[i][j][k][1] = -MAXL;
dp[0][0][0][0] = dp[0][0][0][1] = 0;
int h = 0;
for (i = 0; i <= n; i++) {
for (j = 0; j <= m; j++) {
if (i == n && j == m) continue;
for (k = 0; k <= mc; k++) {
maxu(dp[1 - h][j][k][0], dp[h][j][k][0]);
maxu(dp[h][j + 1][b[j + 1].c][0], dp[h][j][k][0]);
maxu(dp[h][j + 1][0][0], dp[h][j][k][0]);
maxu(dp[h][j + 1][k][1], dp[h][j][k][1]);
maxu(dp[1 - h][j][a[i + 1].c][1], dp[h][j][k][1] - a[i + 1].v);
maxu(dp[1 - h][j][0][1], dp[h][j][k][1]);
if (k == 0) continue;
if (i < n && a[i + 1].f >= b[j].f) {
if (a[i + 1].c >= k) {
maxu(dp[1 - h][j][a[i + 1].c - k][1], dp[h][j][k][0] + b[j].v - a[i + 1].v);
}
if (a[i + 1].c <= k) {
maxu(dp[1 - h][j][k - a[i + 1].c][0], dp[h][j][k][0] - a[i + 1].v + (a[i + 1].c == k ? b[j].v : 0));
}
}
if (j < m && a[i].f >= b[j + 1].f) {
if (k >= b[j + 1].c) {
maxu(dp[h][j + 1][k - b[j + 1].c][1], dp[h][j][k][1] + b[j + 1].v);
}
if (k <= b[j + 1].c) {
maxu(dp[h][j + 1][b[j + 1].c - k][0], dp[h][j][k][1] + (k == b[j + 1].c ? b[j + 1].v : 0));
}
}
}
}
if (i < n) for (j = 0; j <= m + 1; j++) for (k = 0; k <= mc + 1; k++) dp[h][j][k][0] = dp[h][j][k][1] = -MAXL;
h = 1 - h;
}
h = 1 - h;
ll ans = dp[h][m][0][0];
for (i = 0; i <= mc; i++) maxu(ans, dp[h][m][i][1]);
cout << ans << "\n";
return;
}
void precalc()
{
return;
}
int main()
{
fastio();
precalc();
int tests = 1, tc;
//cin >> tests;
for (tc = 1; tc <= tests; tc++) {
solve();
}
//cout << db(clock()) / CLOCKS_PER_SEC << endl;
return 0;
}
/*
# # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # #
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
452 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
13 ms |
3664 KB |
Output is correct |
6 |
Correct |
14 ms |
3668 KB |
Output is correct |
7 |
Correct |
14 ms |
3796 KB |
Output is correct |
8 |
Correct |
16 ms |
3796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
8 ms |
340 KB |
Output is correct |
6 |
Correct |
5 ms |
340 KB |
Output is correct |
7 |
Correct |
13 ms |
388 KB |
Output is correct |
8 |
Correct |
15 ms |
440 KB |
Output is correct |
9 |
Correct |
15 ms |
412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
6 ms |
340 KB |
Output is correct |
4 |
Correct |
12 ms |
3412 KB |
Output is correct |
5 |
Correct |
1624 ms |
3480 KB |
Output is correct |
6 |
Correct |
1775 ms |
3860 KB |
Output is correct |
7 |
Correct |
1781 ms |
3860 KB |
Output is correct |
8 |
Correct |
1704 ms |
3840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
57 ms |
764 KB |
Output is correct |
4 |
Correct |
52 ms |
2440 KB |
Output is correct |
5 |
Correct |
1412 ms |
3868 KB |
Output is correct |
6 |
Correct |
1783 ms |
3844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
452 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
13 ms |
3664 KB |
Output is correct |
6 |
Correct |
14 ms |
3668 KB |
Output is correct |
7 |
Correct |
14 ms |
3796 KB |
Output is correct |
8 |
Correct |
16 ms |
3796 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
8 ms |
340 KB |
Output is correct |
14 |
Correct |
5 ms |
340 KB |
Output is correct |
15 |
Correct |
13 ms |
388 KB |
Output is correct |
16 |
Correct |
15 ms |
440 KB |
Output is correct |
17 |
Correct |
15 ms |
412 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
596 KB |
Output is correct |
24 |
Correct |
2 ms |
724 KB |
Output is correct |
25 |
Correct |
2 ms |
724 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
6 ms |
340 KB |
Output is correct |
29 |
Correct |
12 ms |
3412 KB |
Output is correct |
30 |
Correct |
1624 ms |
3480 KB |
Output is correct |
31 |
Correct |
1775 ms |
3860 KB |
Output is correct |
32 |
Correct |
1781 ms |
3860 KB |
Output is correct |
33 |
Correct |
1704 ms |
3840 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
2 ms |
468 KB |
Output is correct |
36 |
Correct |
57 ms |
764 KB |
Output is correct |
37 |
Correct |
52 ms |
2440 KB |
Output is correct |
38 |
Correct |
1412 ms |
3868 KB |
Output is correct |
39 |
Correct |
1783 ms |
3844 KB |
Output is correct |
40 |
Correct |
103 ms |
1252 KB |
Output is correct |
41 |
Correct |
319 ms |
2404 KB |
Output is correct |
42 |
Correct |
43 ms |
2900 KB |
Output is correct |
43 |
Correct |
1716 ms |
3864 KB |
Output is correct |
44 |
Correct |
1718 ms |
3916 KB |
Output is correct |
45 |
Correct |
1434 ms |
3904 KB |
Output is correct |
46 |
Correct |
19 ms |
2000 KB |
Output is correct |
47 |
Correct |
45 ms |
2896 KB |
Output is correct |
48 |
Correct |
49 ms |
2900 KB |
Output is correct |