제출 #1360579

#제출 시각아이디문제언어결과실행 시간메모리
1360579fgggCloud Computing (CEOI18_clo)C++20
100 / 100
362 ms2236 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
void solve() {
    // dp[i][x] = dp[i + 1][x]
    // dp[i][x] = dp[i + 1][x - c[j]] - v[i];
    // dp[i][x] = dp[i + 1][x + c[j]] + c[i]
    ll n;
    cin >> n;;
    vector<array<ll, 4>> a(n);
    for (ll i = 0; i < n; i++) {
        ll c, f, v;
        cin >> c >> f >> v;
        a[i] = {f, 1, c, v};
    }
    ll m;
    cin >> m;
    for (ll i = 0; i < m; i++) {
        ll c, f, v;
        cin >> c >> f >> v;
        a.push_back({f, -1, c, v});
    }
    sort(all(a));
    vector<ll> dp(n * 50 + 1, -1e18), pdp(n * 50 + 1, -1e18);
    for (ll i = n + m - 1; i > -1; i--) {
        if (a[i][1] == 1) {
            if (i == n + m - 1) {
                dp[0] = 0;
                dp[a[i][2]] = -a[i][3];
            } else {
                for (ll x = 0; x <= n * 50; x++) {
                    dp[x] = pdp[x];
                    if (x >= a[i][2]) {
                        dp[x] = max(dp[x], pdp[x - a[i][2]] - a[i][3]);
                    }
                }
            }
        } else {
            if (i == n + m - 1) {
                dp[0] = 0;
            } else {
                for (ll x = 0; x <= n * 50; x++) {
                    dp[x] = pdp[x];
                    if (x + a[i][2] <= n * 50) {
                        dp[x] = max(dp[x], pdp[x + a[i][2]] + a[i][3]);
                    }
                }
            }
        }
        pdp = dp;
        dp.assign(n * 50 + 1, -1e18);
    }
    ll mx = 0;
    for (ll x = 0; x <= n * 50; x++) mx = max(mx, pdp[x]);
    cout << mx;
}
signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…