Submission #19078

#	Time	Username	Problem	Language	Result	Execution time	Memory
19078		Namnamseo	달리는 게임 (kriii3_E)	C++14	70 / 70	284 ms	47960 KiB

E

#include <cstdio>
typedef long long ll;
int n;
ll data[1000010];
ll P [1000010];
ll S [1000010];
ll dp[1000010];

ll a [1000010];
ll b [1000010];
int ln;

inline double crossing(ll a,ll b,ll c,ll d){
    return double(d-b)/(a-c);
}

inline double crossing(int l1,int l2){
    return crossing(a[l1],b[l1],a[l2],b[l2]);
}

void addline(ll grad,ll yint){
    while(ln>=2){
        if(crossing(ln-2,ln-1)<=
           crossing(a[ln-1],b[ln-1],grad,yint)){
            //puts("line pop");
            --ln;
        } else break;
    }
    a[ln]=grad; b[ln]=yint; ++ln;
}

ll get(ll x){
    if(ln==1) return a[0]*x+b[0];
    int l=0, r=ln-2, mid;
    double LP=crossing(0,1);
    double RP=crossing(r,r+1);
    if(LP<x) return a[0]*x+b[0];
    if(x<RP) return a[r+1]*x+b[r+1];
    while(l+1<r){
        mid=(l+r)/2;
        if(crossing(mid,mid+1)>=x) l=mid;
        else r=mid;
    }
    return a[r]*x+b[r];
}

template<typename T> inline T max(T a,T b){ return b<a?a:b; }
template<typename T> inline T min(T a,T b){ return a<b?a:b; }

int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;++i) 
        scanf("%lld",data+i),
        P[i]=P[i-1]+  data[i],
        S[i]=S[i-1]+i*data[i];
    addline(0,0);
    for(i=1;i<=n;++i){
        dp[i]=max(dp[i-1],S[i]+get(P[i]));
        //printf("dp[%d]=%lld\n",i,dp[i]);
        //printf("Adding line %dx + %lld\n",-i, dp[i]-S[i]+i*P[i]);
        addline(-i, dp[i]-S[i]+i*P[i]);
    }
    printf("%lld\n",dp[n]);
    return 0;
}

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