#include<bits/stdc++.h>
#define LL long long
#define Re register LL
using namespace std;
const LL inf=1000,N=20;
LL vis[inf+5];char A[N+5],B[N+5];
inline LL fu(){return rand()%2?-1:1;}
inline LL Rand(LL L,LL R){
LL a=R-L+1;
LL b=(LL)rand()*rand()%a+1;
b=b*rand()%a+1;
b=b*rand()%a+1;
b=b*rand()%a+1;
b=b*rand()%a+1;
return L+b-1;
}
LL lo[N],tp[N];
int main(){
// freopen("data.in","w",stdout);
srand(time(0));
Re n=rand()%N+1;
printf("%lld 0\n",n);
for(Re i=1;i<=n;++i)printf("%lld ",Rand(1,inf));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3;
const LL inf=4e18+5;
int n,opt,A[N],B[N];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct QAQ0{
int x;LL g[N],S[N],dp[N];
inline void sakura(){
for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,dp[i]=inf;
dp[0]=0,g[0]=S[0];
for(Re i=1,p=0;i<=n;++i){
while(p+1<i&&2*S[p+1]-g[p+1]<=S[i])++p;
dp[i]=dp[p]+(S[i]-S[p])*(S[i]-S[p]),g[i]=S[p];
// printf("i=%d, p=%d\n",i,p);
// for(Re j=0;j<=p;++j)
// if(dp[i]>=(tmp=dp[j]+(S[i]-S[j])*(S[i]-S[j])))
// dp[i]=tmp,g[i]=S[j];
}
// for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);
printf("%lld\n",dp[n]);
}
}T0;
int main(){
// freopen("456.txt","r",stdin);
in(n),in(opt);
if(n<=5000)T0.sakura();
fclose(stdin);
fclose(stdout);
return 0;
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3;
const LL inf=4e18+5;
int n,opt,A[N],B[N];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct QAQ0{
int x,g[N];LL tmp,S[N],dp[N];
inline void sakura(){
for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,dp[i]=inf;
dp[0]=0,g[0]=0;
for(Re i=1,p=0;i<=n;/*printf("i=%d, p=%d\n",i,p),*/++i)
for(Re j=0;j<i;++j)
if(S[i]-S[j]>=S[j]-S[g[j]]&&dp[i]>=(tmp=dp[j]+(S[i]-S[j])*(S[i]-S[j])))
dp[i]=tmp,g[i]=j,p=j;
// for(Re i=0;i<=n;++i)printf("dp[%d]=%lld\n",i,dp[i]);
printf("%lld\n",dp[n]);
}
}T0;
int main(){
// freopen("456.txt","r",stdin);
in(n),in(opt);
if(n<=5000)T0.sakura();
fclose(stdin);
fclose(stdout);
return 0;
}
#include<bits/stdc++.h>
#include<windows.h>
#define Re register int
using namespace std;
int main(){
Re sec=0.1,HYJ=0;// 随机数据生成时间,大约每0.1秒一次
sec*=1e3;
while(1){
printf("第 %d 组数据:\n",++HYJ);
system("data.exe>data.in");// 随机数据生成到文件
system("std.exe<data.in>std.out");// 运行标准程序
system("myprogram.exe<data.in>my.out");// 运行自己的程序(可能全WA但能跑通的程序)
if(system("fc std.out my.out")){// 比较输出文件,fc比较文本文件不同返回1
system("pause");
printf("[corrupted string]");
//break;
}
Sleep(sec);
}
}