#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
void chmax(ll &a, ll b) { a = max(a, b); }
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<int> C(n), F(n), V(n);
for (int i=0; i<n; i++) cin >> C[i] >> F[i] >> V[i];
int m;
cin >> m;
vector<int> qC(m), qF(m), qV(m);
for (int i=0; i<m; i++) cin >> qC[i] >> qF[i] >> qV[i];
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) -> bool {
return F[i] > F[j];
});
vector<int> qOrder(m);
iota(qOrder.begin(), qOrder.end(), 0);
sort(qOrder.begin(), qOrder.end(), [&](int i, int j) -> bool {
return qF[i] > qF[j];
});
const int CC = 100'000;
vector dp(m+1, vector<ll>(CC+1, -inf));
for (int j=0; j<=m; j++) {
dp[j][0] = 0;
}
for (int i=0; i<n; i++) {
int ii = order[i];
for (int j=m-1; j>=0; j--) {
int jj = qOrder[j];
// add core on this row
if (F[ii] >= qF[jj]) {
for (int k=CC; k>=0; k--) {
chmax(dp[j][min(CC,k+C[ii])], dp[j][k] - V[ii]);
}
}
// take a subset and use it
for (int k=qC[jj]; k<=CC; k++) {
chmax(dp[j+1][k-qC[jj]], dp[j][k] + qV[jj]);
}
}
// take any subset onto the next row
for (int j=0; j<m; j++) {
for (int k=0; k<=CC; k++) {
chmax(dp[j+1][k], dp[j][k]);
}
}
}
// answer can be from any dp cell
ll ans = -inf;
for (int j=0; j<=m; j++) {
for (int k=0; k<=CC; k++) {
chmax(ans, dp[j][k]);
}
}
cout << ans << "\n";
return 0;
}
# | 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... |