Submission #704611

#	Time	Username	Problem	Language	Result	Execution time	Memory
704611		Cyanmond	Cloud Computing (CEOI18_clo)	C++17	100 / 100	582 ms	2264 KiB

clo

#include <bits/stdc++.h>

using i64 = long long;
constexpr int X = 50;
constexpr i64 inf = 1ll << 50;

void chmax(i64 &a, i64 b) {
    a = std::max(a, b);
}

struct CPU {
    int cores;
    i64 rate;
    i64 price;
    bool operator<(const CPU &other) {
        return rate < other.rate;
    }
};

int main() {
    int N;
    std::cin >> N;
    std::vector<CPU> stores(N);
    for (auto &[c, r, p] : stores) {
        std::cin >> c >> r >> p;
    }
    int M;
    std::cin >> M;
    std::vector<CPU> customers(M);
    for (auto &[c, r, p] : customers) {
        std::cin >> c >> r >> p;
    }
    std::sort(stores.begin(), stores.end());
    std::sort(customers.begin(), customers.end());
    std::vector<std::pair<CPU, bool>> data;
    int id = 0;
    for (int i = 0; i < N; ++i) {
        while (id != M and customers[id].rate <= stores[i].rate) {
            data.push_back({customers[id++], false});
        }
        data.push_back({stores[i], true});
    }
    while (id != M) {
        data.push_back({customers[id++], false});
    }
    const int U = N + M;

    std::vector<i64> dp(M * X + 1, -inf);
    dp[0] = 0;
    for (int i = 0; i < U; ++i) {
        auto ndp = dp;
        const auto &[cpu, type] = data[i];
        if (type) {
            // store
            for (int j = M * X; j >= 0; --j) {
                chmax(ndp[std::max(0, j - cpu.cores)], dp[j] - cpu.price);
            }
        } else {
            for (int j = 0; j <= M * X - cpu.cores; ++j) {
                chmax(ndp[j + cpu.cores], dp[j] + cpu.price);
            }
        }
        dp = std::move(ndp);
    }
    std::cout << dp[0] << std::endl;
}

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