#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];
});
// ill try subtask 4 first
// dp[i][j]: only consider orders with index <= i
// and we have a coresum of j currently, what's the max profit
// but like we can just do this same thing but we sort q in ascending frequency
// and only add the cores to the rows which they are allowed on??
vector dp(m+1, vector<ll>(51, -inf));
dp[0][0] = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
int jj = qOrder[j];
// add core on this row
if (F[i] >= qF[jj]) {
for (int k=50-C[i]; k>=0; k--) {
chmax(dp[j][k+C[i]], dp[j][k] - V[i]);
}
}
// take any subset onto the next row
for (int k=0; k<=50; k++) {
chmax(dp[j+1][k], dp[j][k]);
}
// take a subset and use it
for (int k=qC[jj]; k<=50; k++) {
chmax(dp[j+1][k-qC[jj]], dp[j][k] + qV[jj]);
}
}
}
// answer can be from any dp cell
ll ans = -inf;
for (int j=0; j<=m; j++) {
for (int k=0; k<=50; 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... |