Submission #15440

#	Time	Username	Problem	Language	Result	Execution time	Memory
15440		gs13068	달리는 게임 (kriii3_E)	C++98	70 / 70	270 ms	35936 KiB

E

#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]);
}

• Subtask 1: 26 / 26
• Subtask 2: 44 / 44