Submission #5522

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
5522	2014-05-05 12:24:46	gs12117	Split the sequence (APIO14_sequence)	C++98	100 / 100	620 ms	86328 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
int n,m;
int a[100100];
long long int b[100100];
long long int dp[100100];
long long int ndp[100100];
int cutp[210][100100];
int deq[100100];
int cut[210];
int qs,qe;
int main(){
    int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i+1]=b[i]+a[i];
    }
    for(i=0;i<=n;i++){
        dp[i]=b[i]*b[i];
    }
    for(i=0;i<m;i++){
        ndp[0]=0;
        deq[0]=0;
        qs=0;
        qe=1;
        for(j=1;j<=n;j++){
            while(qs+1<qe&&dp[deq[qs]]+(b[j]-b[deq[qs]])*(b[j]-b[deq[qs]])>=dp[deq[qs+1]]+(b[j]-b[deq[qs+1]])*(b[j]-b[deq[qs+1]]))qs++;
            ndp[j]=dp[deq[qs]]+(b[j]-b[deq[qs]])*(b[j]-b[deq[qs]]);
            cutp[i+1][j]=deq[qs];
            while(qs+1<qe&&((long double)b[j]-b[deq[qe-1]])*(dp[deq[qe-1]]+b[deq[qe-1]]*b[deq[qe-1]]-dp[deq[qe-2]]-b[deq[qe-2]]*b[deq[qe-2]])>=((long double)b[deq[qe-1]]-b[deq[qe-2]])*(dp[j]+b[j]*b[j]-dp[deq[qe-1]]-b[deq[qe-1]]*b[deq[qe-1]]))qe--;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29