Submission #599158

#	Time	Username	Problem	Language	Result	Execution time	Memory
599158		isaachew	Cloud Computing (CEOI18_clo)	C++17	100 / 100	545 ms	2016 KiB

clo

#include <bits/stdc++.h>
/*
 Start 14:37 PM
 All tasks are performed simultaneously
 ~ 100000 cores
 
 Price up to 10^9; binsearch?
 O(nm log n log m)
 
 ST1: ?
 ST2: ?
 ST3: Potential O(n^3)
 One-to-one match between machines and customers
 Start highest computer first
 Buying/selling events
 
 Number of computers,
 
 ST4: There is only a number of cores. DP for min cost over number of cores to sell and buy in O(n sum(c_i) + m sum(C_j))
 ST5:
 */
struct obj{
    int cores;
    int power;
    int cost;
    obj(int a,int b,int c):cores(a),power(b),cost(c){}
};

std::vector<obj> comps;
std::vector<obj> reqs;
int main(){
    int n,m,nc=0;
    std::cin>>n;
    std::vector<int> sorted;
    
    for(int i=0;i<n;i++){
        int c,f,v;
        std::cin>>c>>f>>v;
        comps.push_back(obj(c,f,v));
        sorted.push_back(i);
        nc+=c;
    }
    std::cin>>m;
    for(int i=0;i<m;i++){
        int c,f,v;
        std::cin>>c>>f>>v;
        reqs.push_back(obj(c,f,v));
        sorted.push_back(~i);
    }
    std::sort(sorted.begin(),sorted.end(),[](int a,int b){
        int csa=a>=0?comps[a].power:reqs[~a].power;
        int csb=b>=0?comps[b].power:reqs[~b].power;
        return csa==csb?a>b:csa>csb;
    });
    std::vector<long long> dp(nc+1,-(1ll<<62));
    dp[0]=0;
    for(int i=0;i<n+m;i++){
        std::vector<long long> dp_new(dp);
        int cur=sorted[i];
        if(cur>=0){
            //std::cout<<"cost "<<comps[cur].cost<<" computer\n";
            for(int j=nc;j>=comps[cur].cores;j--){
                dp_new[j]=std::max(dp[j],dp[j-comps[cur].cores]-comps[cur].cost);
            }
        }else{
            cur=~cur;
            //std::cout<<"cost "<<reqs[cur].cost<<" customer\n";
            for(int j=0;j<=nc-reqs[cur].cores;j++){
                dp_new[j]=std::max(dp[j],dp[j+reqs[cur].cores]+reqs[cur].cost);
            }
        }
        dp=dp_new;
        /*
        for(long long i:dp){
            std::cout<<i<<' ';
        }
        std::cout<<'\n';
         */
    }
    long long mx=0;
    for(int i=0;i<nc;i++){
        mx=std::max(mx,dp[i]);
    }
    
    std::cout<<mx<<'\n';
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10