Submission #1261432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261432		doq	Cloud Computing (CEOI18_clo)	C++20	100 / 100	220 ms	1316 KiB

clo

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

const int MAX_CORES = 100000 + 6;
const ll INF = 1e18;

struct Item {
    int c, f, v;
};

bool compare(const Item &a, const Item &b) {
    if (a.f == b.f) {
        return a.v < b.v;
    }
    return a.f > b.f;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<Item> items;
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        items.push_back({c, f, -v});
    }
    
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        items.push_back({-c, f, v});
    }
    
    sort(items.begin(), items.end(), compare);
    
    ll dp[MAX_CORES];
    fill_n(dp, MAX_CORES, -INF);
    dp[0] = 0;
    int total_cores = 0;
    
    for (const auto &item : items) {
        if (item.c > 0) {
            for (int j = total_cores; j >= 0; j--) {
                if (dp[j] != -INF) {
                    int new_j = j + item.c;
                    if (new_j < MAX_CORES) {
                        dp[new_j] = max(dp[new_j], dp[j] + item.v);
                    }
                }
            }
            total_cores += item.c;
        } else {
            int req_cores = -item.c;
            for (int j = req_cores; j <= total_cores; j++) {
                if (dp[j] != -INF) {
                    dp[j - req_cores] = max(dp[j - req_cores], dp[j] + item.v);
                }
            }
        }
    }
    
    ll ans = 0;
    for (int i = 0; i <= total_cores; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    
    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