Submission #1099227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099227		ortsac	Cloud Computing (CEOI18_clo)	C++17	0 / 100	2 ms	5980 KiB

clo

#include <bits/stdc++.h>

using namespace std;

#define dp(i, j, k, l) trueDP[l][k][i][j]

const int MAXN = 255;
const int INF = 0x3f3f3f3f;

int trueDP[2][55][20][2005];
int mx[MAXN][MAXN];

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";
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10