Submission #1242478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242478		chienthanminh23	Cloud Computing (CEOI18_clo)	C++17	0 / 100	50 ms	328 KiB

clo

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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

struct Core {
    int freq, cost, id;
    bool operator<(const Core& o) const {
        return freq > o.freq; // Sort descending by frequency
    }
};

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

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

    int n, m;
    cin >> n;

    vector<Core> cores;
    for (int i = 0; i < n; ++i) {
        int c, f, v;
        cin >> c >> f >> v;
        for (int j = 0; j < c; ++j) {
            cores.push_back({f, v, i});
        }
    }

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

    int totalCores = cores.size();
    sort(cores.begin(), cores.end());

    ll maxProfit = 0;
    int totalStates = 1 << m;

    // Try all combinations of orders (up to 2^15 = 32k)
    for (int mask = 0; mask < totalStates; ++mask) {
        vector<Order> selected;
        ll orderValue = 0;
        int totalRequired = 0;

        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                selected.push_back(orders[i]);
                orderValue += orders[i].value;
                totalRequired += orders[i].cores;
            }
        }

        if (totalRequired > totalCores)
            continue;

        vector<bool> used(totalCores, false);
        int assigned = 0;

        // Copy of cores, sorted by freq descending
        vector<Core> available = cores;

        bool valid = true;
        for (auto& ord : selected) {
            int needed = ord.cores;
            int count = 0;

            for (int i = 0; i < totalCores && count < needed; ++i) {
                if (!used[i] && available[i].freq >= ord.minFreq) {
                    used[i] = true;
                    count++;
                }
            }

            if (count < needed) {
                valid = false;
                break;
            }
        }

        if (!valid)
            continue;

        ll totalCost = 0;
        set<int> usedMachines;
        for (int i = 0; i < totalCores; ++i) {
            if (used[i]) {
                usedMachines.insert(cores[i].id);
            }
        }
        for (int id : usedMachines) {
            // Add the cost of using machine `id`
            for (int i = 0; i < n; ++i) {
                if (id == i) {
                    int c, f, v;
                    cin >> c >> f >> v;
                    totalCost += v;
                    break;
                }
            }
        }

        maxProfit = max(maxProfit, orderValue - totalCost);
    }

    cout << maxProfit << "\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