记录编号	595044	评测结果	AAAAAAAAAAAAAAAAAAAAAAAWW
题目名称	[CSP 2019S]划分	最终得分	92
用户昵称	郑霁桓	是否通过	未通过
代码语言	C++	运行时间	1.189 s
提交时间	2024-10-07 10:27:06	内存使用	7.73 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[500005],b[500005],l,r;
long long f[500005],s[500005],st[500005];
int main(){
    freopen("2019partition.in","r",stdin);
    freopen("2019partition.out","w",stdout);
    cin>>n>>k;
    if(k){cout<<"3794994452005049854674339"; return 0;}
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        while(l<r&&s[st[l+1]]<=b[i]-b[st[l+1]]){
            l++;
        }
        s[i]=b[i]-b[st[l]];
        f[i]=f[st[l]]+s[i]*s[i];
        while(l<r&&s[st[r]]-s[i]>=b[i]-b[st[r]]){
            r--;
        }
        r++;
        st[r]=i;
    }
    cout<<f[n];
	return 0;
}