Submission #1191824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191824		sunboi	Cloud Computing (CEOI18_clo)	C++20	0 / 100	1 ms	396 KiB

clo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

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

    int n;  
    cin >> n;
    vector<tuple<int,int,ll>> comps(n);
    ll totalC = 0;
    set<int> freq;
    for(int i=0;i<n;i++){
        int ci; ll fi, vi;
        cin >> ci >> fi >> vi;
        comps[i] = make_tuple(ci, (int)fi, vi);
        totalC += ci;
        freq.insert(fi);
    }
    int m;
    cin >> m;
    vector<tuple<int,int,ll>> orders(m);
    for(int j=0;j<m;j++){
        int Cj; ll Fj, Vj;
        cin >> Cj >> Fj >> Vj;
        orders[j] = make_tuple(Cj, (int)Fj, Vj);
        freq.insert(Fj);
    }
    // compress and sort frequencies descending
    vector<int> Freq(freq.begin(), freq.end());
    sort(Freq.rbegin(), Freq.rend());

    // group computers and orders by frequency
    unordered_map<int, vector<int>> comp_by_f;
    for(int i=0;i<n;i++){
        auto &[ci, fi, vi] = comps[i];
        comp_by_f[fi].push_back(i);
    }
    unordered_map<int, vector<int>> ord_by_f;
    for(int j=0;j<m;j++){
        auto &[Cj, Fj, Vj] = orders[j];
        ord_by_f[Fj].push_back(j);
    }

    // DP arrays
    int MAXC = totalC;
    vector<ll> minCost(MAXC+1, INF), orderDP(MAXC+1, -INF);
    minCost[0] = 0;
    orderDP[0] = 0;

    ll answer = 0;
    // sweep frequencies
    for(int f: Freq){
        // add all computers with fi == f
        for(int idx: comp_by_f[f]){
            auto &[ci, fi, vi] = comps[idx];
            for(int c = MAXC - ci; c >= 0; --c){
                if(minCost[c] < INF){
                    minCost[c + ci] = min(minCost[c + ci], minCost[c] + vi);
                }
            }
        }
        // add all orders with Fj == f
        for(int idx: ord_by_f[f]){
            auto &[Cj, Fj, Vj] = orders[idx];
            for(int c = MAXC; c >= Cj; --c){
                orderDP[c] = max(orderDP[c], orderDP[c - Cj] + Vj);
            }
        }
        // update answer at this frequency threshold
        for(int c = 0; c <= MAXC; ++c){
            if(minCost[c] < INF && orderDP[c] > -INF){
                answer = max(answer, orderDP[c] - minCost[c]);
            }
        }
    }

    cout << answer << "\n";
    return 0;
}

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