Submission #1324118

#TimeUsernameProblemLanguageResultExecution timeMemory
1324118sh_qaxxorov_571Cloud Computing (CEOI18_clo)C++20
100 / 100
237 ms1336 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Item {
    int cores, freq, price, type; // type: 1 - kompyuter, -1 - buyurtma
};

bool compareItems(const Item& a, const Item& b) {
    if (a.freq != b.freq) return a.freq > b.freq;
    return a.type > b.type; // Chastota teng bo'lsa, avval kompyuterni ko'ramiz
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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, 1});
    }

    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, -1});
    }

    sort(items.begin(), items.end(), compareItems);

    int max_cores = n * 50;
    // DP massivini juda kichik son bilan to'ldiramiz
    vector<ll> dp(max_cores + 1, -2e18); 
    dp[0] = 0;

    for (auto& item : items) {
        if (item.type == 1) { // Kompyuter sotib olish
            for (int k = max_cores; k >= item.cores; k--) {
                dp[k] = max(dp[k], dp[k - item.cores] - item.price);
            }
        } else { // Buyurtmani qabul qilish
            for (int k = 0; k <= max_cores - item.cores; k++) {
                dp[k] = max(dp[k], dp[k + item.cores] + item.price);
            }
        }
    }

    ll ans = 0;
    for (int k = 0; k <= max_cores; k++) ans = max(ans, dp[k]);
    cout << ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...