Submission #1125098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125098		Pannda	Cloud Computing (CEOI18_clo)	C++20	100 / 100	1406 ms	2148 KiB

clo

#include <bits/stdc++.h>
using namespace std;

const int N = 2000, M = 2000, C = 50;
const long long INF = 2e18;
long long dp[2][M + 1][C + 1];

void toMax(long long &x, long long y) {
    if (y > x) x = y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<array<int, 3>> supplies(n); // (power, number, cost)
    for (int i = 0; i < n; i++) {
        cin >> supplies[i][1] >> supplies[i][0] >> supplies[i][2];
    }
    int m;
    cin >> m;
    vector<array<int, 3>> orders(m); // (power, number, cost)
    for (int i = 0; i < m; i++) {
        cin >> orders[i][1] >> orders[i][0] >> orders[i][2];
    }

    sort(supplies.begin(), supplies.end(), greater<>());
    sort(orders.begin(), orders.end(), greater<>());

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j <= m; j++) {
            for (int c = 0; c <= C; c++) {
                dp[i][j][c] = -INF;
            }
        }
    }
    dp[0][0][0] = 0;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int c = 0; c <= C; c++) {
                if (i < n)
                    toMax(dp[1][j][c], dp[0][j][c]);
                if (j < m)
                    toMax(dp[0][j + 1][c], dp[0][j][c]);
                if (i < n && c + supplies[i][1] <= C)
                    toMax(dp[1][j][c + supplies[i][1]], dp[0][j][c] - supplies[i][2]);
                if (j < m && i > 0 && orders[j][0] <= supplies[i - 1][0] && c - orders[j][1] >= 0)
                    toMax(dp[0][j + 1][c - orders[j][1]], dp[0][j][c] + orders[j][2]);
                if (i < n && j < m && orders[j][0] <= supplies[i][0] && c + supplies[i][1] - orders[j][1] >= 0 && c + supplies[i][1] - orders[j][1] <= C)
                    toMax(dp[1][j + 1][c + supplies[i][1] - orders[j][1]], dp[0][j][c] - supplies[i][2] + orders[j][2]);
            }
        }
        if (i < n)
        for (int j = 0; j <= m; j++) {
            for (int c = 0; c <= C; c++) {
                dp[0][j][c] = dp[1][j][c];
                dp[1][j][c] = -INF;
            }
        }
    }

    long long ans = 0;
    for (int c = 0; c <= 50; c++) {
        toMax(ans, dp[0][m][c]);
    }
    cout << ans << '\n';

}

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