oj.uz

Submission #19076

# Submission time Handle Problem Language Result Execution time Memory
19076 2016-02-18T03:50:40 Z Namnamseo 달리는 게임 (kriii3_E) C++14
0 / 70
 0 ms 5772 KB 
#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.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5772 KB Output is correct
2 Incorrect 0 ms 5772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -