제출 #1275968

#제출 시각아이디문제언어결과실행 시간메모리
1275968uranium235Cloud Computing (CEOI18_clo)C++17
90 / 100
232 ms1356 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct item {
    int c, f, v;
    bool computer;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    vector<item> a;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        a.push_back({c, f, v, true});
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        a.push_back({c, f, v, false});
    }
    sort(a.begin(), a.end(), [](const item &l, const item &r) -> bool {
        return make_pair(r.f, r.computer) < make_pair(l.f, l.computer);
    });
    int b = 50 * n;
    vector<ll> dp(b, LONG_LONG_MIN / 2);
    dp[0] = 0;
    for (int i = 0; i < n + m; i++) {
        if (a[i].computer) {
            for (int j = b - 1 - a[i].c; j >= 0; j--) {
                dp[j + a[i].c] = max(dp[j + a[i].c], dp[j] - a[i].v);
            }
        } else {
            for (int j = a[i].c; j < b; j++) {
                dp[j - a[i].c] = max(dp[j - a[i].c], dp[j] + a[i].v);
            }
        }
    }
    ll ans = 0;
    for (ll i : dp) ans = max(ans, i);

    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...