제출 #599158

#제출 시각아이디문제언어결과실행 시간메모리
599158isaachewCloud Computing (CEOI18_clo)C++17
100 / 100
545 ms2016 KiB
#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'; }
#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...