Submission #1161239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161239		marcus06	Cloud Computing (CEOI18_clo)	C++20	100 / 100	468 ms	2956 KiB

clo

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

#ifdef LOCAL
#include </home/marcus06/vimcp/Library/debug.h>
#else
#define debug(...) 
#endif

const lli INF = 1e18 + 7;
using triplet = array <int, 3>;

void solve() {
    int N; cin >> N;
    vector <triplet> computers(N);
    int numCores = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) cin >> computers[i][j];
        computers[i][2] *= -1;
        numCores += computers[i][0];
    }
    sort(computers.begin(), computers.end(), [&](triplet i, triplet j) {
        return i[1] > j[1];
    });

    int M; cin >> M;
    vector <triplet> orders(M);
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < 3; ++j) cin >> orders[i][j];
        orders[i][0] *= -1;
    }
    sort(orders.begin(), orders.end(), [&](triplet i, triplet j) {
        return i[1] > j[1];
    });

    vector <triplet> newSet;
    int j = 0;
    for (int i = 0; i < N; ++i) {
        while (j < M && orders[j][1] > computers[i][1]) {
            newSet.emplace_back(orders[j]);
            j++;
        }
        newSet.emplace_back(computers[i]);
    }
    while (j < M) {
        newSet.emplace_back(orders[j]);
        j++;
    }

    int newSize = N + M;
    vector <vector <lli>> dp(2, vector <lli> (numCores + 1, -INF));
    dp[0][0] = 0;
    for (int i = 0; i < newSize; ++i) {
        int cur = i & 1;
        int nxt = (i + 1) & 1;
        //dp[cur][0] = max(dp[cur][0], (lli) 0);
        auto [c, f, v] = newSet[i];
        for (int j = 0; j <= numCores; ++j) {
            dp[nxt][j] = max(dp[nxt][j], dp[cur][j]);
            if (0 <= j + c && j + c <= numCores) {
                dp[nxt][j + c] = max(dp[nxt][j + c], dp[cur][j] + v);
            }
        }
    }

    lli ans = 0;
    for (int i = 0; i <= numCores; ++i) {
        ans = max(ans, dp[newSize & 1][i]);
    }

    cout << ans << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif

    int tt = 1;
    while (tt--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
    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