Submission #1091508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091508		xthappy	Cloud Computing (CEOI18_clo)	C++14	0 / 100	1 ms	348 KiB

clo

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 2005;
const int MAXC = 55;
const long long INF = 1e18;

struct Computer {
    int cores, freq;
    long long price;
};

struct Order {
    int cores, freq;
    long long price;
};

int n, m;
vector<Computer> computers;
vector<Order> orders;
long long dp[MAXN][MAXC];

long long solve() {
    sort(computers.begin(), computers.end(), [](const Computer& a, const Computer& b) {
        return a.freq > b.freq;
    });
    
    sort(orders.begin(), orders.end(), [](const Order& a, const Order& b) {
        return a.freq > b.freq;
    });

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < MAXC; j++) {
            dp[i][j] = -INF;
        }
    }
    dp[0][0] = 0;

    int computerIndex = 0;
    for (int orderIndex = 0; orderIndex <= m; orderIndex++) {
        while (computerIndex < n && (orderIndex == m || computers[computerIndex].freq >= orders[orderIndex].freq)) {
            for (int j = MAXC - 1; j >= computers[computerIndex].cores; j--) {
                for (int k = 0; k <= orderIndex; k++) {
                    dp[k][j] = max(dp[k][j], dp[k][j - computers[computerIndex].cores] - computers[computerIndex].price);
                }
            }
            computerIndex++;
        }

        if (orderIndex < m) {
            for (int j = MAXC - 1; j >= orders[orderIndex].cores; j--) {
                for (int k = orderIndex; k >= 0; k--) {
                    dp[k + 1][j] = max(dp[k + 1][j], dp[k][j - orders[orderIndex].cores] + orders[orderIndex].price);
                }
            }
        }
    }

    long long maxProfit = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j < MAXC; j++) {
            maxProfit = max(maxProfit, dp[i][j]);
        }
    }
    return maxProfit;
}

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

   
    cin >> n;
    computers.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> computers[i].cores >> computers[i].freq >> computers[i].price;
    }

    cin >> m;
    orders.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> orders[i].cores >> orders[i].freq >> orders[i].price;
    }

    cout << solve() << endl;

    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