Submission #549257

#	Time	Username	Problem	Language	Result	Execution time	Memory
549257		Alexandruabcde	Cloud Computing (CEOI18_clo)	C++14	100 / 100	421 ms	1284 KiB

clo

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int CORESMAX = 50 * 2000 + 5;
constexpr LL INF = 1LL * 1e16;

struct Computer {
    int cores;
    int freq;
    int value;
    int ind;

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

int N, M;
vector <Computer> E;
LL dp[CORESMAX];
int Total_Cores;

void Read () {
    cin >> N;

    for (int i = 1; i <= N; ++ i ) {
        Computer C;
        cin >> C.cores >> C.freq >> C.value;
        C.ind = -1;

        Total_Cores += C.cores;
        E.push_back(C);
    }

    cin >> M;
    for (int i = 1; i <= M; ++ i ) {
        Computer C;
        cin >> C.cores >> C.freq >> C.value;
        C.ind = 1;
        E.push_back(C);
    }

    sort(E.begin(), E.end());
}

void Solve () {
    for (int i = 0; i <= Total_Cores; ++ i )
        dp[i] = -INF;
    dp[0] = 0;

    for (auto it : E) {
        if (it.ind == -1) {
            for (int i = Total_Cores; i >= it.cores; -- i ) {
                if (dp[i - it.cores] == -INF) continue;

                dp[i] = max(dp[i], dp[i - it.cores] - it.value);
            }
        }
        else {
            for (int i = 0; i <= Total_Cores - it.cores; ++ i ) {
                if (dp[i + it.cores] == -INF) continue;

                dp[i] = max(dp[i], dp[i + it.cores] + it.value);
            }
        }
    }

    LL ans = 0;
    for (int i = 0; i <= Total_Cores; ++ i )
        ans = max(ans, dp[i]);

    cout << ans << '\n';
}

int main () {
    Read();
    Solve();

    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