제출 #1277759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277759		haithamcoder	Cloud Computing (CEOI18_clo)	C++20	72 / 100	929 ms	2880 KiB

clo

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

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

struct item {
    ll c, f, v;
};

void shift(vector<vector<ll>>& dp) {
    ll sz = dp[0].size();

    for (ll i = 0; i < sz; i++) {
        dp[0][i] = dp[1][i];
        dp[1][i] = -inf;
    }
}

int main() {
    Algerian OI

    ll n, m;
    cin >> n;

    vector<item> a(n);

    for (ll i = 0; i < n; i++) cin >> a[i].c >> a[i].f >> a[i].v;

    cin >> m;

    vector<item> b(m);

    for (ll i = 0; i < m; i++) cin >> b[i].c >> b[i].f >> b[i].v;

    vector<item> tr;

    for (auto [c, f, v] : a) {
        tr.push_back({c, f, -v});
    }

    for (auto [c, f, v] : b) {
        tr.push_back({-c, f, v});
    }

    sort(tr.begin(), tr.end(), [&](item x, item y) -> bool {
        return x.f > y.f;
    });

    
    ll k = n + m;

    
    vector<vector<ll>> dp(2, vector<ll>(50 * n + 1, -inf));
    dp[0][0] = 0;
    ll res = 0;

    for (ll i = 0; i < k; i++) {
        auto [c, f, v] = tr[i];
        for (ll j = 50 * n; j >= 0; j--) {
            dp[1][j] = max(dp[0][j], dp[1][j]);
            if (j + c <= 50 * n && j + c >= 0) dp[1][j + c] = max(dp[1][j + c], dp[0][j] + v);
        }

        shift(dp);
    }

    for (ll i = 0; i <= 50 * n; i++) {
        res = max(res, dp[0][i]);
    }

    cout << res << "\n";

    return 0;
}

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