oj.uz

Submission #18608

# Submission time Handle Problem Language Result Execution time Memory
18608 2016-02-11T07:41:03 Z eaststar Split the sequence (APIO14_sequence) C++14
0 / 100
 0 ms 18676 KB 
#include <stdio.h>
int q[100010];
long long a[100010],D[210][10010];
int main(){
    int i,j,n,k,f,r;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)scanf("%lld",a+i),a[i]+=a[i-1],D[0][i]=-a[i]*a[i];
    for(i=1;i<=k;++i){
        q[f=r=1]=i;
        for(j=i+1;j<=n;++j){
            while(f<r&&a[q[f]]*a[j]+D[i-1][q[f]]<=a[q[f+1]]*a[j]+D[i-1][q[f+1]])++f;
            D[i][j]=a[q[f]]*a[j]+D[i-1][q[f]]-a[j]*a[j];
            while(f<r&&(D[i-1][q[r]]-D[i-1][q[r-1]])*(a[q[r-1]]-a[j])>(D[i-1][j]-D[i-1][q[r-1]])*(a[q[r-1]]-a[q[r]]))--r;
            q[++r]=j;
        }
    }
    printf("%lld",D[k][n]+a[n]*a[n]);
    return 0;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 18676 KB Output isn't correct - wrong output format : Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

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

Subtask #3
0.0 / 11.0

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

Subtask #4
0.0 / 17.0

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

Subtask #5
0.0 / 21.0

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

Subtask #6
0.0 / 29.0

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