Submission #1242483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242483		chienthanminh23	Cloud Computing (CEOI18_clo)	C++17	0 / 100	3094 ms	736 KiB

clo

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

#define ll long long
const ll INF = 1e18;

struct Computer {
    int cores, freq;
    ll cost;
};

struct Order {
    int cores, minFreq;
    ll value;
};

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

    int n, m;
    cin >> n;
    vector<Computer> computers(n);
    for (int i = 0; i < n; ++i) {
        cin >> computers[i].cores >> computers[i].freq >> computers[i].cost;
    }

    cin >> m;
    vector<Order> orders(m);
    for (int i = 0; i < m; ++i) {
        cin >> orders[i].cores >> orders[i].minFreq >> orders[i].value;
    }

    ll answer = 0;

    // Try all subsets of computers (up to 2000)
    // But instead, use bounded knapsack to choose computers

    // dp[f][c] = min cost to get c cores using only computers with freq >= f
    // frequency values range up to 1e9 but only small number of unique freq used
    vector<int> freqs;
    for (auto& c : computers) freqs.push_back(c.freq);
    sort(freqs.begin(), freqs.end());
    freqs.erase(unique(freqs.begin(), freqs.end()), freqs.end());

    unordered_map<int, vector<Computer>> freq_computers;
    for (auto& c : computers) {
        freq_computers[c.freq].push_back(c);
    }

    for (auto& order : orders) {
        int fmin = order.minFreq;
        int cneed = order.cores;

        // Build list of all cores with freq >= fmin
        vector<pair<int, ll>> allCores; // (cores, cost)

        for (auto& comp : computers) {
            if (comp.freq >= fmin) {
                allCores.push_back({comp.cores, comp.cost});
            }
        }

        // Bounded knapsack: minimize cost to get >= cneed cores
        int maxC = 0;
        for (auto& p : allCores) maxC += p.first;
        if (maxC < cneed) continue; // not enough cores

        vector<ll> dp(maxC + 1, INF);
        dp[0] = 0;

        for (auto& p : allCores) {
            int cnt = p.first;
            ll cost = p.second;
            // Bounded knapsack optimization using power-of-two trick
            for (int k = 1; cnt > 0; k <<= 1) {
                int use = min(k, cnt);
                cnt -= use;
                for (int j = maxC; j >= use; --j) {
                    if (dp[j - use] != INF) {
                        dp[j] = min(dp[j], dp[j - use] + cost);
                    }
                }
            }
        }

        // Try getting at least cneed cores
        ll minCost = INF;
        for (int i = cneed; i <= maxC; ++i) {
            minCost = min(minCost, dp[i]);
        }

        if (minCost < INF) {
            answer = max(answer, order.value - minCost);
        }
    }

    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