Submission #398992

#	Time	Username	Problem	Language	Result	Execution time	Memory
398992		KoD	Cloud Computing (CEOI18_clo)	C++17	100 / 100	299 ms	1984 KiB

clo

#include <bits/stdc++.h>

using ll = long long;

template <class T>
using Vec = std::vector<T>;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

struct State {
    int c, f, v;
    bool t;
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    Vec<State> state;
    for (int i = 0; i < N; ++i) {
        int c, f, v;
        std::cin >> c >> f >> v;
        state.push_back(State{c, f, v, false});
    }
    int Q;
    std::cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int c, f, v;
        std::cin >> c >> f >> v;
        state.push_back(State{c, f, v, true});
    }
    std::sort(state.begin(), state.end(), [&](const State& a, const State& b) {
        if (a.f != b.f) return a.f > b.f;
        return b.t;
    });
    Vec<ll> dp(1, 0);
    for (const auto [c, f, v, t]: state) {
        if (t) {
            for (int i = c; i < (int) dp.size(); ++i) {
                dp[i - c] = std::max(dp[i - c], dp[i] + v);
            }
        }
        else {
            const int cur = (int) dp.size();
            dp.resize(cur + c, -INF);
            for (int i = cur - 1; i >= 0; --i) {
                dp[i + c] = std::max(dp[i + c], dp[i] - v);
            }
        }
    }
    std::cout << *std::max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

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