Submission #678910

#	Time	Username	Problem	Language	Result	Execution time	Memory
678910		bebra	Cloud Computing (CEOI18_clo)	C++17	100 / 100	902 ms	2772 KiB

clo

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


struct Computer {
    int cores_n;
    int freq;
    int price;
    int type;

    Computer(int _cores_n = 0, int _freq = 0, int _price = 0, int _type = -1)
        : cores_n(_cores_n), freq(_freq), price(_price), type(_type) {}

    bool operator<(const Computer& other) const {
        if (freq == other.freq) {
            return type > other.type;
        }
        return freq < other.freq;
    }

    friend istream& operator>>(istream& is, Computer& obj) {
        is >> obj.cores_n >> obj.freq >> obj.price;
        return is;
    }
    friend ostream& operator<<(ostream& os, const Computer& obj) {
        os << obj.type << ' ' << obj.cores_n << ' ' << obj.freq << ' ' << obj.price;
        return os;
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Computer> a;
    a.reserve(n * 4);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        Computer comp;
        cin >> comp;
        comp.type = 1;
        a.push_back(comp);
        sum += comp.cores_n;
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        Computer comp;
        cin >> comp;
        comp.type = 2;
        a.push_back(comp);
    }
    sort(a.rbegin(), a.rend());
    const int MAX_K = sum;
    const long long MINUS_INF = (long long)(-1e13);
    vector<vector<long long>> dp(2, vector<long long>(MAX_K + 1, MINUS_INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n + m; ++i) {
        for (int j = 0; j <= MAX_K; ++j) {
            dp[i & 1][j] = MINUS_INF;
            if (a[i - 1].type == 1) {
                dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j]);
                if (j - a[i - 1].cores_n >= 0) {
                    dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j - a[i - 1].cores_n] - a[i - 1].price);
                }
            } else if (a[i - 1].type == 2) {
                dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j]);
                if (j + a[i - 1].cores_n <= MAX_K) {
                    dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j + a[i - 1].cores_n] + a[i - 1].price);
                }
            }
        }
    }
    long long ans = 0;
    for (int j = 0; j <= MAX_K; ++j) {
        ans = max(ans, dp[(n + m) & 1][j]);
    }
    cout << ans << '\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