Submission #972903

#TimeUsernameProblemLanguageResultExecution timeMemory
972903efedmrlrCloud Computing (CEOI18_clo)C++17
100 / 100
445 ms2132 KiB
#include <bits/stdc++.h>

#define lli long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

const int N = 1e5 + 5;
const lli INF = 1e17;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int n, m;
vector<array<int, 3> > p;
vector<lli> dp(N, -INF), dpn(N);
void solve() {
    cin >> n;
    REP(i, n) {
        int c, f, v;
        cin >> c >> f >> v;
        p.pb({f, c, -v});
    }
    cin >> m;
    REP(i, m) {
        int c, f, v;
        cin >> c >> f >> v;
        p.pb({f, -c, v});
    }
    sort(rall(p));
    dp[0] = 0;
    for(int i = 0; i < n + m; i++) {
        for(int c = 0; c < N; c++) {
            dpn[c] = dp[c];
            if(0 <= c - p[i][1] && c - p[i][1] < N) {
                dpn[c] = max(dpn[c], dp[c - p[i][1]] + p[i][2]);
            }
        }
        swap(dp, dpn);
    }
    lli ans = 0;
    for(int i = 0; i < N; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";


}

signed main() {
    fastio();
    solve();
}
#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...