记录编号	594993	评测结果	AAAAAAAAAAAAAAAAAAAAAAEEE
题目名称	[CSP 2019S]划分	最终得分	88
用户昵称	darkMoon	是否通过	未通过
代码语言	C++	运行时间	2.354 s
提交时间	2024-10-06 20:53:08	内存使用	13.13 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IN = freopen("2019partition.in", "r", stdin);
auto OUT = freopen("2019partition.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 5e5 + 5;
int n = mread(), type = mread(), a[N], f[N][2], s[N];
signed main(){
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = f[0][1] = 0;
    int p = 0;
    deque<pair<int, int> > q;
    for(int i = 1; i <= n; i ++){
        while(q.size() && q.front().fi <= s[i]){
            p = q.front().se;
            q.pop_front();
        }
        f[i][0] = s[i] - s[p];
        f[i][1] = f[p][1] + f[i][0] * f[i][0];
        while(q.size() && q.back().fi >= f[i][0] + s[i]){
            q.pop_back();
        }
        // printf("*** %lld %lld %lld %lld\n", i, p + 1, f[i][0] + s[i], s[i]);
        q.push_back(mp(f[i][0] + s[i], i));
    }
    printf("%lld", f[n][1]);
    return 0;
}