#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
long long c, f, w, tip;
node(long long c = 0, long long f = 0, long long w = 0, long long tip = 0) {
this->c = c;
this->f = f;
this->w = w;
this->tip = tip;
}
};
bool cmp(node a, node b) {
return (a.f < b.f) || (a.f == b.f && a.tip < b.tip);
}
int main() {
long long n;
cin >> n;
vector<node> v(n);
for (long long i = 0; i < n; i++) {
cin >> v[i].c >> v[i].f >> v[i].w;
v[i].tip = 1;
}
long long m;
cin >> m;
for (long long i = 0; i < m; i++) {
long long c, f, w;
cin >> c >> f >> w;
v.push_back(node(c, f, w, 0));
}
long long siz = 7000 + 1;
long long inf = 1e18;
sort(v.begin(), v.end(), cmp);
reverse(v.begin(), v.end());
vector<vector<long long>> dp(v.size() + 1, vector<long long>(siz, -inf));
dp[0][0] = 0;
long long ans = 0;
for (long long i = 0; i < v.size(); i++) {
dp[i + 1] = dp[i];
for (long long x = 0; x < siz; x++) {
if (v[i].tip == 1 && dp[i][max(x - v[i].c, (long long)0)] != -inf) {
dp[i + 1][x] = max(dp[i][x], dp[i][max(x - v[i].c, (long long)0)] - v[i].w);
}
if (v[i].tip == 0 && dp[i][x + v[i].c] != -inf) {
dp[i + 1][x] = max(dp[i][x], dp[i][x + v[i].c] + v[i].w);
}
ans = max(ans, dp[i + 1][x]);
}
}
cout << ans;
}
# | 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... |