[Apio2014]序列分割

#include<cstdio>
#include<iostream>
#define N 100001
using namespace std;
long long sum[N],now[N],last[N];
int head,tail,q[N],a[N];
void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); }
}
long long up(int k,int j)
{
    return last[j]-last[k]-sum[j]*sum[j]+sum[k]*sum[k];
}
long long down(int k,int j)
{
    return sum[k]-sum[j];
}
int main()
{
    int n,k;
    read(n); read(k); k++;
    for(int i=1;i<=n;i++) read(a[i]);
    int tot=0;
    for(int i=1;i<=n;i++) if(a[i]) sum[++tot]=a[i];
    for(int i=1;i<=tot;i++) sum[i]+=sum[i-1];
    int j;
    long long ans=0;
    for(int K=2;K<=k;K++)
    {
        head=1; tail=1; q[1]=K-1;
        for(int i=K;i<=tot;i++)
        {
            while(head<tail && up(q[head],q[head+1])>=down(q[head],q[head+1])*sum[i]) head++;
            j=q[head];
            now[i]=last[j]+sum[j]*(sum[i]-sum[j]);
            while(head<tail && up(q[tail-1],q[tail])*down(q[tail],i)>=up(q[tail],i)*down(q[tail-1],q[tail])) tail--;
            q[++tail]=i;
        }
        ans=max(ans,now[tot]);
        swap(now,last);
    }
    printf("%lld",ans);
}