This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define dp(i, j, k, l) trueDP[l][k][i][j]
const int MAXN = 20;
const int MAXM = 2005;
const int INF = 0x3f3f3f3f;
int trueDP[2][55][MAXN][MAXM];
int mx[MAXN][MAXM];
struct O {
int c, f, v;
O(int x = 0, int y = 0, int z = 0) : c(x), f(y), v(z) {}
bool operator < (const O& a) {
return (make_pair(f, make_pair(c, v)) < make_pair(a.f, make_pair(a.c, a.v)));
}
};
int32_t main() {
int n, m;
cin >> n;
vector<O> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i].c >> a[i].f >> a[i].v;
cin >> m;
vector<O> b(m + 1);
for (int i = 1; i <= n; i++) cin >> b[i].c >> b[i].f >> b[i].v;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= 51; k++) {
for (int l = 0; l < 2; l++) dp(i, j, k, l) = -INF;
}
}
}
dp(0, 0, 0, 0) = 0;
dp(1, 0, 0, 0) = 0;
dp(0, 1, 0, 0) = 0;
dp(0, 0, 0, 1) = 0;
dp(1, 0, 0, 1) = 0;
dp(0, 1, 0, 1) = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// calc for dp[i][j][k][0]
if ((a[i].c >= b[j].c) && (a[i].f >= b[j].f)) dp(i, j, a[i].c - b[j].c, 0) = (mx[i - 1][j - 1] + b[j].v - a[i].v);
dp(i, j, a[i].c, 0) = max(dp(i, j, a[i].c, 0), mx[i - 1][j] - a[i].v);
for (int k = 0; k <= a[i].c; k++) {
dp(i, j, k, 0) = max(dp(i, j, k, 0), dp(i, j - 1, k, 0)); // skip j
if (((k + b[j].c) <= a[i].c) && (a[i].f >= b[j].f)) dp(i, j, k, 0) = max(dp(i, j, k, 0), dp(i, j - 1, k + b[j].c, 0) + b[j].v);
if (a[i].f >= b[j].f) dp(i, j, k, 0) = max(dp(i, j, k, 0), dp(i - 1, j, a[i].c - k, 1) + b[j].v - a[i].v);
mx[i][j] = max(mx[i][j], dp(i, j, k, 0));
}
// calc for dp[i][j][k][1]
if ((a[i].c <= b[j].c) && (a[i].f >= b[j].f)) dp(i, j, b[j].c - a[i].c, 1) = (mx[i - 1][j - 1] - a[i].v);
dp(i, j, b[j].c, 1) = max(dp(i, j, b[j].c, 1), mx[i][j - 1] - a[i].v);
for (int k = b[j].c; k >= 0; k--) {
dp(i, j, k, 1) = max(dp(i, j, k, 1), dp(i - 1, j, k, 1)); // skip i
if (((k + a[i].c) <= b[j].c) && (a[i].f >= b[j].f)) dp(i, j, k, 1) = max(dp(i, j, k, 1), dp(i - 1, j, k + a[i].c, 1) - a[i].v);
if (a[i].f >= b[j].f) dp(i, j, k, 1) = max(dp(i, j, k, 1), dp(i, j - 1, b[j].c - k, 0));
mx[i][j] = max(mx[i][j], dp(i, j, k, 1));
}
mx[i][j] = max(mx[i][j], mx[i - 1][j - 1]);
mx[i][j] = max(mx[i][j], mx[i - 1][j]);
mx[i][j] = max(mx[i][j], mx[i][j - 1]);
}
}
cout << mx[n][m] << "\n";
}
# | 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... |