Title

Description

Input

Sample Input

Input 1:

5 2

4 2 6 1 3

Input 2:

5 3

4 2 6 1 3

Output

Sample Output

output 1:

0

output 2:

24

Data Constraint

Hint

First I only got 70 points QAQ
Another 30 too lazy to hit QAQ because it is another algorithm
Observe the equation of this question
∑ki=1(si−savg)2
∑ki=1si2−(2∗savg∗sum[n]−k∗savg2)
At the same time savg=sum[n]k
So we can get after taking K*K
(∑ki=1si)∗k2−sum[n]2∗k
This is the answer we require
At the same time, Sum [n] indicates that the number from 1 to N
Then it is easy to find that the latter section is the fixed value, so what we require is the minimum value of the previous paragraph
After the beginning of the enumeration, the problem becomes a number of sections. Divide it into K section, and find the smallest number of each paragraph.
dp[i,j]=min(dp[t,j−1]+(sum[i]−sum[t])2)
We can use slope to optimize the efficiency of this DP to O (N)
Because this thing can be converted into
yi = t+k*xi form
Then if you use J to transfer it better than K (j> k), there is

The left side of the
dp1[j]+sum[j]2−dp1[k]−sum[k]2<=sum[i]∗2(sum[j]−sum[k])
formula is not related to I, and the right side can be seen as a constant item
Because Sum [i] is monotonous, so if this formula is established, K will be useless again after the establishment of it.
Then we want to let point I join the queue, set xi, j = 2*(sum [i] -sum [j]), yi, j = dp1 [i]+sum [i]^2-dp1 [j] -sum [j]^2
So if Yi,aXi,a<Ya,bXa,b

Post code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

const int maxn=100005;

ll b[maxn],a[maxn],t[maxn],dp[maxn],sum[maxn],dp1[maxn];
int i,j,l,m,n,tail,head;
ll ans,k;
ll gety(int x,int y){
    return dp1[x]-dp1[y]+sum[x]*sum[x]-sum[y]*sum[y];
}
ll getx(int x,int y){
    return 2*(sum[x]-sum[y]);
}
ll getans(int x,int y){
    return dp1[y]+(sum[x]-sum[y])*(sum[x]-sum[y]);
}
int main(){
    //freopen("4984.in","r",stdin);
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;i++) scanf("%d",&b[i]);
    ans=0x7fffffff;
    for (i=1;i<=n;i++){
        for (j=i;j<=n;j++) a[j-i+1]=b[j];
        for (j=1;j<=i-1;j++) a[n-i+j+1]=b[j];
        sum[0]=0;
        for (j=1;j<=n;j++){
            sum[j]=sum[j-1]+a[j];
            dp1[j]=sum[j]*sum[j];
        }
        for (j=2;j<=k;j++){
            head=0;
            tail=1;
            t[0]=dp[0]=0;
            for (l=1;l<=n;l++){
                while (head+1<tail && gety(t[head+1],t[head])<=sum[l]*getx(t[head+1],t[head])) head++;
                dp[l]=getans(l,t[head]);
                while (head+1<tail && 
                       gety(l,t[tail-1])*getx(t[tail-1],t[tail-2])<=gety(t[tail-1],t[tail-2])*getx(l,t[tail-1]))
                       tail--;
                t[tail]=l;
                tail++;
            }
            for (l=1;l<=n;l++) dp1[l]=dp[l];
        }
        ans=min(ans,(k*k*dp[n]-k*sum[n]*sum[n]));
    }
    printf("%d\n",ans);
}