Submission #1270486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270486		osmiyum	Cloud Computing (CEOI18_clo)	C++20	100 / 100	398 ms	2196 KiB

clo

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

struct Item {
    int cores;       // bilgisayar için +ci, müşteri için -Cj
    long long val;   // bilgisayar için -vi, müşteri için +Vj
    long long f;     // clock rate (fi veya Fj)
};

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

    int n; cin >> n;
    vector<Item> all;

    // bilgisayarlar
    for (int i = 0; i < n; i++) {
        int c; long long f, v;
        cin >> c >> f >> v;
        all.push_back({c, -v, f});
    }

    int m; cin >> m;
    // müşteriler
    for (int i = 0; i < m; i++) {
        int C; long long F, V;
        cin >> C >> F >> V;
        all.push_back({-C, V, F});
    }

    // sıralama: büyükten küçüğe f, eşit f’de bilgisayarlar önde
    sort(all.begin(), all.end(), [](const Item &a, const Item &b) {
        if (a.f != b.f) return a.f > b.f;
        return a.cores > b.cores; // bilgisayar (+) öne
    });

    // toplam core kapasitesi
    int MAXC = 0;
    for (auto &it : all) if (it.cores > 0) MAXC += it.cores;

    const long long NEG = -4e18;
    vector<long long> dp(MAXC+1, NEG);
    dp[0] = 0;

    for (auto &it : all) {
        vector<long long> ndp = dp; // yeni durum

        if (it.cores >= 0) {
            // bilgisayar alınıyor: core ekleniyor
            for (int j = 0; j <= MAXC - it.cores; j++) {
                if (dp[j] != NEG) {
                    ndp[j + it.cores] = max(ndp[j + it.cores], dp[j] + it.val);
                }
            }
        } else {
            int need = -it.cores;
            // müşteri kabul ediliyor: core azalıyor
            for (int j = need; j <= MAXC; j++) {
                if (dp[j] != NEG) {
                    ndp[j - need] = max(ndp[j - need], dp[j] + it.val);
                }
            }
        }
        dp.swap(ndp);
    }

    long long ans = 0;
    for (long long v : dp) ans = max(ans, v);
    cout << ans << "\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