Submission #1306471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306471		__moin__	Cloud Computing (CEOI18_clo)	C++20	100 / 100	629 ms	2112 KiB

clo

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

#define ll long long

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    vector<tuple<int,int,int,int>> entries;  // freq, type, cores, profit
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int c, f, v; cin >> c >> f >> v;
        entries.emplace_back(-f, 0, c, -v);
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int c, f, v; cin >> c >> f >> v;
        entries.emplace_back(-f, 1, -c, v);
    }
    sort(entries.begin(), entries.end());

    vector<ll> dp(max(n, m)*50+1, -1e18);
    dp[0] = 0;
    for (int i = 0; i < n+m; i++) {
        auto [f, t, c, p] = entries[i];
        vector<ll> newdp(dp.begin(), dp.end());
        for (int C = 0; C < dp.size(); C++) {
            if (C-c < 0) continue;
            if (C-c >= dp.size()) continue;
            newdp[C] = max(newdp[C], dp[C-c] + p);
        }
        dp = newdp;
    }

    // vector<vector<ll>> dp(n+m+1, vector<ll>(max(n, m)*50+1, -1e18));
    // dp[0][0] = 0;
    // for (int i = 0; i < n+m; i++) {
    //     auto [f, t, c, p] = entries[i];
    //     dp[i+1] = vector<ll>(dp[i].begin(), dp[i].end());
    //     for (int C = 0; C < dp[0].size(); C++) {
    //         if (C-c < 0) continue;
    //         if (C-c >= dp[0].size()) continue;
    //         dp[i+1][C] = max(dp[i+1][C], dp[i][C-c] + p);
    //     }
    // }

    // for (int i = 0; i <= n+m; i++) {
    //     for (ll e : dp[i] | ranges::views::take(32)) {
    //         if (e < -1e9) cout << "-oo ";
    //         else cout << e << " ";
    //     }
    //     cout << "\n";
    // }

    cout << *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