Submission #15440

#TimeUsernameProblemLanguageResultExecution timeMemory
15440gs13068달리는 게임 (kriii3_E)C++98
70 / 70
270 ms35936 KiB
#include<cstdio> #include<set> long long a[1111111]; long long s[1111111]; long long ss[1111111]; long long d[1111111]; std::set<std::pair<long long,long long> > S; std::set<std::pair<long long,long long> >::iterator it1,it2; std::pair<long long,long long> P; int main() { double tx,ty; int i,j,n; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%lld",&a[i]); S.insert(std::make_pair(0,0)); for(i=n;i>=0;i--) { s[i]=s[i+1]+a[i]; ss[i]=ss[i+1]+s[i+1]; while(S.size()>=2) { it1=S.end(); it1--; it2=it1; it2--; if(i*it1->first+it1->second>i*it2->first+it2->second)break; S.erase(it1); } it1=S.end(); it1--; d[i]=i*it1->first+it1->second+ss[i]; P=std::make_pair(s[i],d[i]-ss[i]-i*s[i]); it1=it2=S.lower_bound(std::make_pair(P.first,-9e18)); if(it1!=S.end()) { if(it1->first==P.first&&it1->second>=P.second)continue; if(it1!=S.begin()) { it2--; tx=-1.*(it1->second-it2->second)/(it1->first-it2->first); ty=it1->first*tx+it1->second; if(ty>=P.first*tx+P.second)continue; } } while(1) { it1=it2=S.lower_bound(std::make_pair(P.first,-9e18)); if(it1==S.end())break; if(it1->first==P.first&&it1->second<=P.second) { S.erase(it1); continue; } it2++; if(it2==S.end())break; tx=-1.*(it1->second-it2->second)/(it1->first-it2->first); ty=it1->first*tx+it1->second; if(ty<=P.first*tx+P.second)S.erase(it1); else break; } while(1) { it1=it2=S.lower_bound(std::make_pair(P.first,-1e18)); if(it1==S.begin())break; it1--; if(it1==S.begin())break; it2=it1; it2--; tx=-1.*(it1->second-it2->second)/(it1->first-it2->first); ty=it1->first*tx+it1->second; if(ty<=P.first*tx+P.second)S.erase(it1); else break; } S.insert(std::make_pair(P.first,P.second)); } printf("%lld\n",d[0]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...