Submission #1300325

#TimeUsernameProblemLanguageResultExecution timeMemory
1300325NipphitchCloud Computing (CEOI18_clo)C++20
100 / 100
512 ms1472 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+5;
const int INF=1e16+7;

int n,m,dp[N+5],ans;
vector <array <int,4>> vec;

bool cmp(array <int,4> x,array <int,4> y){
    auto [c1,f1,v1,t1]=x;
    auto [c2,f2,v2,t2]=y;
    if(f1!=f2) return f1>f2;
    else return t1<t2;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=1;i<N;i++) dp[i]=-INF;
    cin >> n;
    for(int i=1;i<=n;i++){
        int c,f,v;
        cin >> c >> f >> v;
        vec.push_back({c,f,v,0});
    }
    cin >> m;
    for(int i=1;i<=m;i++){
        int c,f,v;
        cin >> c >> f >> v;
        vec.push_back({c,f,v,1});
    }
    sort(vec.begin(),vec.end(),cmp);
    for(auto [c,f,v,t]:vec){
        if(t==1){
            for(int i=0;i<N;i++){
                if(i+c<N) dp[i]=max(dp[i],dp[i+c]+v);
            }
        }
        if(t==0){
            for(int i=N-1;i>=0;i--){
                if(i-c>=0) dp[i]=max(dp[i],dp[i-c]-v);
            }
        }
        for(int i=0;i<N;i++) ans=max(ans,dp[i]);
    }
    cout << ans;
}
#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...