제출 #1360487

#제출 시각아이디문제언어결과실행 시간메모리
1360487fgggCloud Computing (CEOI18_clo)C++20
36 / 100
166 ms327680 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, c, v, 1};
    }
    ll m;
    cin >> m;
    for (ll i = 0; i < m; i++) {
        ll c, f, v;
        cin >> c >> f >> v;
        a.push_back({f, c, v, -1});
    }
    sort(all(a));
    vector<vector<ll>> dp(n + m, vector<ll>(n * 50 + 1, -1e18));
    for (ll i = n + m - 1; i > -1; i--) {
        if (a[i][3] == 1) {
            if (i == n + m - 1) {
                dp[i][0] = 0;
                dp[i][a[i][1]] = -a[i][2];
                continue;
            }
            for (ll x = 0; x <= n * 50; x++) {
                dp[i][x] = dp[i + 1][x];
                if (x >= a[i][1]) {
                    dp[i][x] = max(dp[i][x], dp[i + 1][x - a[i][1]] - a[i][2]);
                }
            }
        } else {
            if (i == n + m - 1) {
                dp[i][0] = 0;
                continue;
            }
            for (ll x = 0; x <= n * 50; x++) {
                dp[i][x] = dp[i + 1][x];
                if (x + a[i][1] <= n * 50) {
                    dp[i][x] = max(dp[i][x], dp[i + 1][x + a[i][1]] + a[i][2]);
                }
            }
        }
    }
    ll mx = 0;
    for (ll x = 0; x <= n * 50; x++) mx = max(mx, dp[0][x]);
    cout << mx;
}
signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…