제출 #1259757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259757		vuviet	Cloud Computing (CEOI18_clo)	C++20	18 / 100	276 ms	1244 KiB

clo

/**
 *  __      __   __      __
 *  \ \    / /   \ \    / (_)     _____
 *   \ \  / /_   _\ \  / / _  ___|_   _|
 *    \ \/ /| | | |\ \/ / | |/ _ \ | |
 *     \  / | |_| | \  /  | |  __/ | |
 *      \/   \__,_|  \/   |_|\____||_|
 *
 *     Author:    ~Noah-kun~
 *     Created:   2025-08-17 19:00
**/

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

#define int long long
#define ____VuViet__ signed main

const int MAXN = 4005;   // vì n+m có thể lên tới 4000
const int MAXC = 100 * 2000 + 5; // mỗi c max 50, n max 2000 => sumc <= 100000
const long long NEG = -4e18;

struct Deal {
    int c, f, v;
    bool operator < (const Deal &o) const {
        if (f == o.f) return v < o.v;
        return f > o.f;
    }
} deals[MAXN];

int dp[MAXC];
int n, m, sumc = 0;

void ReadData() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int c, f, v;
        cin >> c >> f >> v;
        deals[i] = {c, f, -v};
        sumc += c;
    }
    cin >> m;
    for (int i = n + 1; i <= n + m; ++i) {
        int c, f, v;
        cin >> c >> f >> v;
        deals[i] = {-c, f, v};
    }
    sort(deals + 1, deals + n + m + 1);
}

void Solve() {
    for (int i = 0; i <= sumc; ++i) dp[i] = NEG;
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        auto t = deals[i];
        for (int c = sumc; c >= t.c; --c) {
            if (dp[c - t.c] != NEG)
                dp[c] = max(dp[c], dp[c - t.c] + t.v);
        }
    }

    for (int i = n + 1; i <= n + m; ++i) {
        auto t = deals[i];
        for (int c = 0; c <= sumc + t.c && c <= sumc; ++c) {
            if (c - t.c >= 0 && c - t.c <= sumc && dp[c - t.c] != NEG)
                dp[c] = max(dp[c], dp[c - t.c] + t.v);
        }
    }

    cout << *max_element(dp, dp + sumc + 1);
}

____VuViet__() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ReadData();
    Solve();
    return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 18 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10