Submission #1114569

#TimeUsernameProblemLanguageResultExecution timeMemory
1114569akacool445kCloud Computing (CEOI18_clo)C++14
18 / 100
709 ms1920 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
#define pint pair<int, int>
#define vint vector<pair<int, int>>
const int mod = 1e9 + 7;
const int shrek = 4000 * 20;
const int say = INT_MAX;
const int gex = INT_MIN;
const long long oo = 1e18;
// int dp[4001][4000 * 20];
int pre[4000 * 20];
int cur[4000 * 20];
// int temp[4000 * 20];
// int dif = 20 * 4000;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector<array<int, 3>> v;
    int n; cin >> n;
    int maxi = 0;
    for(int i = 0; i < n; i++) {
        int a, b , c; cin >> a >> b >> c;
        v.pb({b, -c, a});
        maxi += a;
    }
    int m; cin >> m;
    for(int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        v.pb({b, c, -a});
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    int len = n + m;
    // for(int i = 0; i <= 4000; i++) {
        for(int j = 0; j < shrek; j++) {
            // dp[i][j] = -1e18;
            pre[j] = -1e18;
            // cur[i] = -1e18;
        }
    // }
    // dp[0][0] = 0;
    pre[0] = 0;
    // cur[0] = 0; d
    for(int i = 1; i <= len; i++) {
        // for(int j = 0; j < shrek; j++) dp[i][j] = dp[i - 1][j];
        for(int j = 0; j < shrek; j++) cur[j] = pre[j];
        
        for(int j = 0; j < shrek; j++) {
            // if(0 <= j + v[i][2] && j + v[i][2] < shrek && dp[i - 1][j] != -1e18) {
            //     dp[i][j + v[i][2]] = max(dp[i - 1][j + v[i][2]], dp[i - 1][j] + v[i][1]);
            // }
            int l = j - v[i][2];
            if(0 <= l && l < shrek && pre[l] != -1e18) {
                cur[j] = max(cur[j], pre[l] + v[i][1]);
            }
        }
        for(int j = 0; j < shrek; j++) pre[j] = cur[j];
        // for(int j = 0; j < shrek; j++) {
        //     pre[j] = cur[j];
        // }
    }
    // int ans = 0;
    // for(int j = 0; j < shrek; j++) {
    //     ans = max(ans, dp[len][j]);
    // }
    int gayans = 0;
    for(int j = 0; j < shrek; j++) {
        gayans = max(gayans, cur[j]);
    }
    // cout << ans << '\n';
    cout << gayans << '\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...