제출 #1345898

#제출 시각아이디문제언어결과실행 시간메모리
1345898kawhietCloud Computing (CEOI18_clo)C++20
100 / 100
323 ms2192 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

#define int long long

constexpr int inf = 1e18;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int sz = 1;
    vector<array<int, 3>> a;
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        sz += c;
        a.push_back({c, f, -v});
    }
    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});
    }
    ranges::sort(a, [&](auto x, auto y) {
        if (x[1] == y[1]) return x[0] > y[0];
        return x[1] > y[1];
    });
    vector<int> dp(sz, -inf);
    dp[0] = 0;
    int ans = 0;
    for (auto [c, f, v] : a) {
        auto dp_nxt = dp;
        for (int i = 0; i < sz; i++) {
            int j = i - c;
            if (j >= 0 && j < sz && dp[j] != -inf) {
                dp_nxt[i] = max(dp_nxt[i], dp[j] + v);
            }
        }
        swap(dp, dp_nxt);
    }
    cout << ranges::max(dp) << '\n';
    return 0;
}
#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...