Submission #1242555

#TimeUsernameProblemLanguageResultExecution timeMemory
1242555glx200Cloud Computing (CEOI18_clo)C++17
100 / 100
707 ms2368 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,a,b) for(int i=a;i<=b;i++)
int const maxN=1e5+5;

struct cost{
    bool type;
    int core;
    ll fre;
    ll val;
};

ll dp1[maxN];
ll dp2[maxN];
bool check1[maxN];
bool check2[maxN];

vector<cost> a;
int n,m;

void process(){
    cin>>n;
    fr(i,1,n){
        int y;
        ll z,t;
        cin>>y>>z>>t;
        a.push_back({true,y,z,-t});
    }
    cin>>m;
    fr(i,1,m){
        int y;
        ll z,t;
        cin>>y>>z>>t;
        a.push_back({false,-y,z,t});
    }
    sort(a.begin(),a.end(),[](cost &A, cost &B){
        if(A.fre==B.fre) return (A.type && !B.type);
        return A.fre > B.fre;
    });
    check1[0]=true;
    fr(i,0,m+n-1){
        int cores=a[i].core;
        ll value=a[i].val;
        fr(j,0,n*50+1){
            if(check1[i]) check2[i]=true;
            if(j+cores >=0 && j+cores<=n*50+1){
                if((dp2[j+cores] < dp1[j]+value || !check2[j+cores]) && check1[j] ){
                    dp2[j+cores]=dp1[j]+value;
                    check2[j+cores]=true;
                }
            }
        }
        fr(j,0,n*50+1){
            check1[j]=check2[j];
            dp1[j]=dp2[j];
        }
    }
    cout<<*max_element(dp1,dp1+n*50+1);
}


int main(){
    process();
}
#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...