제출 #1252710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252710		goldenbull	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1197 ms	3668 KiB

clo

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

const char el = '\n';
const int maxn = 4007;
const int maxc = 50 * maxn;
const ll inf = 1e15 + 7;

struct node {
    int c; ll f, v;
    bool operator<(const node& other) const {
        if (f != other.f) return f > other.f;
        return c > other.c;
    }
};

int n, m;
node T[maxn];
ll dp[2][maxc];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
//    freopen(".inp", "r", stdin);
//    freopen(".out", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int c; ll f, v;
        cin >> c >> f >> v;
        T[i] = {c, f, -v};
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int c; ll f, v;
        cin >> c >> f >> v;
        T[n + i] = {-c, f, v};
    }

    sort(T+1, T+n+m+1);
    fill(dp[0], dp[0]+maxc, -inf);
    dp[0][0] = 0;
    for (int i = 1; i <= n+m; i++) {
        int id = i&1;
        int prev = id^1;
        fill(dp[id], dp[id]+maxc, -inf);

        for (int j = 0; j < maxc; j++) {
            if (dp[prev][j] != -inf) dp[id][j] = dp[prev][j];
            int tmp = j - T[i].c;
            if (tmp >= 0 && tmp < maxc && dp[prev][tmp] != -inf)
                dp[id][j] = max(dp[id][j], dp[prev][tmp] + T[i].v);
        }
    }

    ll res = 0;
    for (int i = 0; i < maxc; i++) res = max(res, dp[(n+m)&1][i]);
    cout << res;

    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