oj.uz

Submission #19078

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 47960 KB Output is correct
2 Correct 0 ms 47960 KB Output is correct
3 Correct 0 ms 47960 KB Output is correct
4 Correct 0 ms 47960 KB Output is correct
5 Correct 0 ms 47960 KB Output is correct
6 Correct 0 ms 47960 KB Output is correct
7 Correct 0 ms 47960 KB Output is correct
8 Correct 0 ms 47960 KB Output is correct
9 Correct 0 ms 47960 KB Output is correct
10 Correct 0 ms 47960 KB Output is correct
11 Correct 0 ms 47960 KB Output is correct
12 Correct 0 ms 47960 KB Output is correct
13 Correct 0 ms 47960 KB Output is correct
14 Correct 0 ms 47960 KB Output is correct
15 Correct 0 ms 47960 KB Output is correct
16 Correct 0 ms 47960 KB Output is correct
17 Correct 0 ms 47960 KB Output is correct
18 Correct 0 ms 47960 KB Output is correct

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47960 KB Output is correct
2 Correct 15 ms 47960 KB Output is correct
3 Correct 15 ms 47960 KB Output is correct
4 Correct 27 ms 47960 KB Output is correct
5 Correct 24 ms 47960 KB Output is correct
6 Correct 19 ms 47960 KB Output is correct
7 Correct 148 ms 47960 KB Output is correct
8 Correct 284 ms 47960 KB Output is correct
9 Correct 262 ms 47960 KB Output is correct