제출 #533819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533819		alextodoran	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1051 ms	1996 KiB

clo

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int NM_MAX = 2000;
const int C_MAX = NM_MAX * 50;
const ll INF = LLONG_MAX / 2;

struct Computer {
    int cores;
    int rate;
    int price;
};
typedef Computer Customer;
bool operator < (const Computer &u, const Computer &v) {
    return u.rate < v.rate;
}

int n, m;
Computer computers[NM_MAX + 2];
Customer customers[NM_MAX + 2];

ll maxProfit[2][C_MAX + 2];

void newComputer (int i) {
    maxProfit[0][C_MAX + 1] = -INF;
    for (int c = C_MAX; c >= 0; c--) {
        ll mx = maxProfit[0][c + 1];
        // Skip computer
        mx = max(mx, maxProfit[1][c]);
        // Buy computer
        mx = max(mx, maxProfit[1][max(0, c - computers[i].cores)] - computers[i].price);
        maxProfit[0][c] = mx;
    }
    swap(maxProfit[0], maxProfit[1]);
}
void newCustomer (int i) {
    maxProfit[0][C_MAX + 1] = -INF;
    for (int c = C_MAX; c >= 0; c--) {
        ll mx = maxProfit[0][c + 1];
        // Skip customer
        mx = max(mx, maxProfit[1][c]);
        // Take customer
        if (c + customers[i].cores <= C_MAX) {
            mx = max(mx, maxProfit[1][c + customers[i].cores] + customers[i].price);
        }
        maxProfit[0][c] = mx;
    }
    swap(maxProfit[0], maxProfit[1]);
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> computers[i].cores;
        cin >> computers[i].rate;
        cin >> computers[i].price;
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> customers[i].cores;
        cin >> customers[i].rate;
        cin >> customers[i].price;
    }
    sort(computers + 1, computers + n + 1);
    sort(customers + 1, customers + m + 1);

    for (int c = 1; c <= C_MAX; c++) {
        maxProfit[1][c] = -INF;
    }
    for (int i = m, j = n + 1; i >= 1; i--) {
        while (j > 1 && computers[j - 1].rate >= customers[i].rate) {
            newComputer(--j);
        }
        newCustomer(i);
    }

    cout << maxProfit[1][0] << "\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