Submission #1094953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094953		ShadowShark	Cloud Computing (CEOI18_clo)	C++17	100 / 100	423 ms	2392 KiB

clo

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

const int maxN = 2e5 + 5;
const long long inf = 1e18;

struct temp {
    int core, rate, price, type;

    bool operator < (const temp& rhs) const {
        if (rate != rhs.rate) return rate > rhs.rate;
        return type < rhs.type;
    }

}query[maxN];

long long dp[2][maxN];

void maximize(long long &u, long long v) {
    if (v > u) u = v;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, sumCores = 0;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> query[i].core >> query[i].rate >> query[i].price;
        query[i].type = 1;
        sumCores = sumCores + query[i].core;
    }

    int m;
    cin >> m;

    for (int i = 1; i <= m; i++) {
        cin >> query[i + n].core >> query[i + n].rate >> query[i + n].price;
        query[i + n].type = 2;
    }

    sort(query + 1, query + n + m + 1);

    for (int i = 0; i <= sumCores; i++)
        dp[0][i] = dp[1][i] = -inf;
    dp[0][0] = 0;

    for (int i = 1; i <= n + m; i++) {
        int curr = i & 1, pre = 1 - curr;
        for (int j = 0; j <= sumCores; j++)
            dp[curr][j] = dp[pre][j];

        if (query[i].type == 1) {
            for (int j = 0; j <= sumCores - query[i].core; j++)
                maximize(dp[curr][j + query[i].core], dp[pre][j] - query[i].price);
        }
        else {
            for (int j = 0; j <= sumCores - query[i].core; j++)
                maximize(dp[curr][j], dp[pre][j + query[i].core] + query[i].price);
        }
    }

    cout << *max_element(dp[(n + m) & 1], dp[(n + m) & 1] + sumCores + 1);
    return 0;
}

/*
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
*/

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