제출 #1057103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057103		_callmelucian	Cloud Computing (CEOI18_clo)	C++14	100 / 100	568 ms	2140 KiB

clo

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct item {
    int core, f;
    ll price;
    bool open;

    item() : core(0), f(0), price(0), open(0) {}
    item (int c, int f, ll p, bool o) : core(c), f(f), price(p), open(o) {}

    bool operator < (const item &o) const {
        if (f == o.f) return open > o.open;
        return f > o.f;
    }
} a[4004];

const int M = 1e5 + 5;
ll dp[2][M];

ll add (ll a, ll b) {
    return (min(a, b) == LLONG_MIN ? LLONG_MIN : a + b);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, sumOpen = 0; cin >> n;
    for (int i = 1; i <= n; i++) {
        int c, f, p; cin >> c >> f >> p;
        a[i] = item(c, f, p, 1), sumOpen += c;
    }
    int m; cin >> m;
    for (int i = n + 1; i <= n + m; i++) {
        int c, f, p; cin >> c >> f >> p;
        a[i] = item(c, f, p, 0);
    }
    sort(a + 1, a + 1 + n + m);

    for (int j = 0; j <= sumOpen; j++) dp[0][j] = LLONG_MIN;
    dp[0][0] = 0;

    for (int i = 1; i <= n + m; i++) {
        int t = i & 1;
        for (int j = 0; j <= sumOpen; j++) dp[t][j] = LLONG_MIN;
        for (int open = 0; open <= sumOpen; open++) {
            dp[t][open] = dp[t ^ 1][open];
            if (a[i].open && open >= a[i].core)
                dp[t][open] = max(dp[t][open], add(dp[t ^ 1][open - a[i].core], - a[i].price));
            if (!a[i].open && open + a[i].core <= sumOpen)
                dp[t][open] = max(dp[t][open], add(dp[t ^ 1][open + a[i].core], a[i].price));
        }
    }

    ll ans = LLONG_MIN;
    for (int open = 0; open <= sumOpen; open++) ans = max(ans, dp[(n + m) & 1][open]);
    cout << ans;

    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