Submission #1192380

#TimeUsernameProblemLanguageResultExecution timeMemory
1192380LithaniumCloud Computing (CEOI18_clo)C++20
100 / 100
237 ms1352 KiB
// buying a computer is + cores - profit
// selling a computer is - cores + profit

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

#define int long long

int dp[100005];

struct Node {
    int c, f, e, type;
};

int32_t main() {
    int N;
    cin >> N;
    vector<Node> nodes;
    for (int i = 1; i <= N; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        nodes.push_back({a, b, c, 0});
    }
    int M;
    cin >> M;
    for (int i = 1; i <= M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        nodes.push_back({a, b, c, 1});
    }
    sort(nodes.begin(), nodes.end(), [](Node a, Node b) {
        if (a.f != b.f) return a.f > b.f;
        return a.type < b.type;
    });
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (Node curr:nodes) {
        if (curr.type == 0) {
            // buy some computers
            for (int i = 100000; i >= 0; i --) {
                dp[i + curr.c] = max(dp[i + curr.c], dp[i] - curr.e);
            }
        } else {
            // sell some computers
            for (int i = curr.c; i <= 100000; i ++) {
                dp[i - curr.c] = max(dp[i - curr.c], dp[i] + curr.e);
            }
        }
    }
    cout << *max_element(dp, dp+100005);
}
#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...