Submission #1283931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283931		algoproclub	Cloud Computing (CEOI18_clo)	C++20	100 / 100	301 ms	1600 KiB

clo

// UUID: 091c0034-8231-4c92-9f6b-6ef003b7fed8
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = (ll)-4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    struct Comp { int c; int f; ll v; };
    vector<Comp> comps(n);
    int totalC = 0;
    for (int i = 0; i < n; ++i) {
        cin >> comps[i].c >> comps[i].f >> comps[i].v;
        totalC += comps[i].c;
    }
    int m; cin >> m;
    struct Ord { int C; int F; ll V; };
    vector<Ord> ords(m);
    for (int j = 0; j < m; ++j) {
        cin >> ords[j].C >> ords[j].F >> ords[j].V;
    }

    // Collect all distinct frequencies that appear in comps or orders
    vector<int> freq;
    freq.reserve(n + m);
    for (auto &co : comps) freq.push_back(co.f);
    for (auto &o : ords) freq.push_back(o.F);
    sort(freq.begin(), freq.end());
    freq.erase(unique(freq.begin(), freq.end()), freq.end());

    // Group comps and orders by frequency
    unordered_map<int, vector<int>> comps_at;
    unordered_map<int, vector<int>> ords_at;
    comps_at.reserve(freq.size()*2);
    ords_at.reserve(freq.size()*2);
    for (int i = 0; i < n; ++i) comps_at[comps[i].f].push_back(i);
    for (int j = 0; j < m; ++j) ords_at[ords[j].F].push_back(j);

    // DP array: dp[c] = max profit with exactly c free cores
    int MAXC = totalC;
    vector<ll> dp(MAXC + 1, NEG), ndp;
    dp[0] = 0;

    // Process frequencies in descending order
    for (int idx = (int)freq.size() - 1; idx >= 0; --idx) {
        int f = freq[idx];

        // add all computers with frequency == f
        if (comps_at.count(f)) {
            for (int id : comps_at[f]) {
                int ci = comps[id].c;
                ll vi = comps[id].v;
                // add this computer (increase cores by ci, subtract cost vi)
                for (int c = MAXC - ci; c >= 0; --c) {
                    if (dp[c] == NEG) continue;
                    dp[c + ci] = max(dp[c + ci], dp[c] - vi);
                }
            }
        }

        // process all orders with required frequency == f
        if (ords_at.count(f)) {
            for (int id : ords_at[f]) {
                int Cj = ords[id].C;
                ll Vj = ords[id].V;
                // accept this order: consume Cj cores and add Vj revenue
                for (int c = Cj; c <= MAXC; ++c) {
                    if (dp[c] == NEG) continue;
                    dp[c - Cj] = max(dp[c - Cj], dp[c] + Vj);
                }
            }
        }
    }

    // final answer: best dp[c] over all c
    ll ans = 0; // profit can be zero as baseline (buy nothing, accept nothing)
    for (int c = 0; c <= MAXC; ++c) {
        if (dp[c] != NEG) ans = max(ans, dp[c]);
    }
    cout << ans << '\n';
    return 0;
}

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