Submission #1268520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268520		extraterrestrial	Cloud Computing (CEOI18_clo)	C++20	100 / 100	488 ms	2132 KiB

clo

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

struct item {
    item() = default;
    item(int _t, int _cnt, int _f, int _cost) : type(_t), cnt(_cnt), f(_f), cost(_cost) {}

    bool operator <(const item &other) const {
        return f > other.f || (f == other.f && type < other.type);
    }

    int type, cnt, f, cost;
};

const long long linf = 1e18;

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

    vector<item> guys;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        guys.emplace_back(0, c, f, v);
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        guys.emplace_back(1, c, f, v);
    }

    sort(guys.begin(), guys.end());
    vector<long long> dp(50 * n + 1, -linf);
    dp[0] = 0;
    for (auto guy : guys) {
        auto new_dp = dp;
        for (int i = 0; i < dp.size(); i++) {
            if (dp[i] == -linf) {
                continue;
            }

            if (guy.type == 0) {
                new_dp[i + guy.cnt] = max(new_dp[i + guy.cnt], dp[i] - guy.cost);
            } else if (i >= guy.cnt) {
                new_dp[i - guy.cnt] = max(new_dp[i - guy.cnt], dp[i] + guy.cost);
            }
        }

        dp.swap(new_dp);
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
}

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