Submission #1314818

#TimeUsernameProblemLanguageResultExecution timeMemory
1314818ChottuFCloud Computing (CEOI18_clo)C++20
100 / 100
257 ms1440 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    vector<array<int,4>> all;
    int n;
    cin >> n;
    
    for (int i = 0; i<n; i++){
        array<int,4> tp;
        int c,f,v;
        cin >> c >> f >> v;
        tp[0] = f;
        tp[1] = 2;
        tp[2] = c;
        tp[3] = v;
        all.push_back(tp);
    }
    int m;
    cin >> m;
    for (int i = 0; i<m; i++){
        array<int,4> tp;
        int c,f,v;
        cin >> c >> f >> v;
        tp[0] = f;
        tp[1] = 1;
        tp[2] = c;
        tp[3] = v;
        all.push_back(tp);
    }
    
    sort(all.begin(),all.end());
    reverse(all.begin(),all.end());
    const int MAXN = 1e5+5;
    const int NINF = -1e18;
    vector<int> dp(MAXN, NINF);
    dp[0] = 0;
    for (auto u : all){
        auto [f, tp, c, v] = u;
        //cout << f << " " << tp << " " << c << " " << v << '\n';
        if (tp == 2){
            for (int j = MAXN-1; j>=0; j--){
                if (j+c < MAXN) dp[j+c] = max(dp[j+c], dp[j]-v);
            }
        }
        if (tp == 1){
            for (int j = 0; j<MAXN; j++){
                if (j-c >= 0) dp[j-c] = max(dp[j-c], dp[j]+v);
            }
        }
    }
    int mx = 0;
    for (int i = 0; i<MAXN; i++){
        mx = max(mx, dp[i]);
    }
    cout << mx;
    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...