qaq

谢谢大家

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
int n,m,sum[3001],f[3001],dp[3001],q[5001],head,tail;
inline double k(int x,int y)
{
    return (f[x]+m*sum[x]*sum[x]+2*sum[n]*sum[x]-f[y]-m*sum[y]*sum[y]-2*sum[n]*sum[y])*1.0/(sum[x]-sum[y]);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(register int i=1;i<=n;++i)
    {
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1];
    }
    for(register int j=1;j<=m;++j)
    {
        memset(q,0,sizeof q);
        head=tail=1;
        for(register int i=1;i<=n;++i)
        {
            while(head<tail&&k(q[head],q[head+1])<2*m*sum[i])
                ++head;
            dp[i]=f[q[head]]+m*(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])-2*sum[n]*(sum[i]-sum[q[head]]);
            while(head<tail&&k(q[tail],i)<k(q[tail-1],q[tail]))
                --tail;
            q[++tail]=i;
        }
        memcpy(f,dp,sizeof dp);
    }
    printf("%lld\n",dp[n]+sum[n]*sum[n]);
    return 0;
}