Submission #19076

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

E

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

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

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

void addline(ll grad,ll yint){
    while(ln>=2){
        if(crossing(a[ln-2],b[ln-2],a[ln-1],b[ln-1])<=
           crossing(a[ln-1],b[ln-1],grad,yint)){
            --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(a[0],b[0],a[1],b[1]);
    double RP=crossing(a[r],b[r],a[r+1],b[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(a[mid],b[mid],a[mid+1],b[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: 0 / 26
• Subtask 2: 0 / 44