Submission #1283953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283953		algoproclub	Cloud Computing (CEOI18_clo)	C++20	100 / 100	298 ms	2112 KiB

clo

// UUID: 4b065467-716e-48f0-8179-020e7b97ca4d
#include <bits/stdc++.h>
using namespace std;
const long long NEG = (long long)-4e18;

struct Comp { 
    int c; int f; long long v; 
    };

struct Ord {
    int C; int F; long long V; 
    };

int main() {
    int n;cin >> n;
    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;
    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;
    for (Comp &co : comps) freq.push_back(co.f);
    for (Ord &o : ords) freq.push_back(o.F);
    sort(freq.begin(), freq.end());
    vector<int> freq2;
    freq2.push_back(-1);
    for (auto i:freq) {
        if (freq2[freq2.size() - 1] != i) freq2.push_back(i);
    }
    freq2.erase(freq2.begin());
    freq = freq2;

    // 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<long long> 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;
                long long 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;
                long long 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
    long long 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