1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2005;
struct Node {
int c, f, v;
bool type;
}a[MAXN * 2];
bool cmp(Node a, Node b) {
if (a.f != b.f) return a.f > b.f;
return a.type < b.type;
}
int n, m, tot;
ll f[MAXN * 50];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d%d", &a[i].c, &a[i].f, &a[i].v), a[i].type = 0, tot += a[i].c;
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &a[n + i].c, &a[n + i].f, &a[n + i].v), a[n + i].type = 1;
sort(a + 1, a + n + m + 1, cmp);
memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n + m; ++i) {
if (a[i].type == 0) {
for (int j = tot; j >= a[i].c; --j)
f[j] = max(f[j], f[j - a[i].c] - a[i].v);
} else {
for (int j = 0; j <= tot - a[i].c; ++j)
f[j] = max(f[j], f[j + a[i].c] + a[i].v);
}
}
ll ans = 0;
for (int i = 0; i <= tot; ++i)
ans = max(ans, f[i]);
printf("%lld", ans);
return 0;
}
|