Submission #1348904

#TimeUsernameProblemLanguageResultExecution timeMemory
1348904biankCloud Computing (CEOI18_clo)C++20
100 / 100
329 ms2912 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back
#define ef emplace_front

#define fst first
#define snd second

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(0);                
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<tuple<int, int, int>> a(n);
    for (auto &[f, c, v] : a) cin >> c >> f >> v, f *= -1;
    
    int m;
    cin >> m;
    vector<tuple<int, int, int>> b(m);
    for (auto &[f, c, v] : b) cin >> c >> f >> v, f *= -1;
    sort(all(a)), sort(all(b));
    
    vll dp = {0LL};
    int p_a = 0, p_b = 0;
    while (p_a < n || p_b < m) {
        if (p_b == m || (p_a < n && get<0>(a[p_a]) <= get<0>(b[p_b]))) {
            auto [f, c, v] = a[p_a++];
            vll newDP(sz(dp) + c, -INF);
            forn(i, sz(dp)) newDP[i] = dp[i];
            forn(i, sz(dp)) newDP[i + c] = max(newDP[i + c], dp[i] - v);
            dp.swap(newDP);
        } else {
            auto [f, c, v] = b[p_b++];
            vll newDP = dp;
            forn(i, sz(dp) - c) newDP[i] = max(newDP[i], dp[i + c] + v);
            dp.swap(newDP);
        }
    }
    cout << *max_element(all(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...