#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,a,b) for(int i = (a); i <= (b); i++)
#define fod(i,a,b) for(int i = (a); i >= (b); i--)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define ll long long
const int N = 2e3 + 5;
const int inf = 1e15;
int n, m;
struct pp {
int fi, se, th;
} b[N * 2];
int nn;
bool cmp(pp a, pp b) {
if(a.se != b.se) return a.se > b.se;
return a.th < b.th;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("1.inp", "r", stdin);
// freopen("1.out", "w", stdout);
cin >> n;
fo(i, 1, n){
int x, y, w; cin >> x >> y >> w;
b[i] = {x, y, -w};
}
cin >> m;
nn = n + m;
fo(i, 1, m) {
int x, y, z; cin >> x >> y >> z;
b[i + n] = {-x, y, z};
}
sort(b + 1, b + nn + 1, cmp);
const int up = 2000 * 50;
vector<int> f(up + 5, -inf);
f[0] = 0;
int sum = 0;
fo(i, 1, nn) {
if(b[i].fi > 0) {
fod(j, sum, 0) if(j + b[i].fi <= up)
f[j + b[i].fi] = max(f[j + b[i].fi], f[j] + b[i].th);
sum += b[i].fi;
} else {
int tmp = -b[i].fi;
fo(j, tmp, sum) {
int now = j - tmp;
f[now] = max(f[now], f[j] + b[i].th);
}
}
}
int res = 0;
fo(i, 0, sum) res = max(res, f[i]);
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |