HNOI2017 礼物
显然，我参加了这次HNOI。
然而并没有什么用，只拿了纯良心的70pts暴力。
30%的数据满足n≤500, m≤10；
70%的数据满足n≤5000；
100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。
并不知道在$30pts$ $m\le 10$的基础上，为什么$100 pts$ $m\le 100$，包括$70 pts$ $m\le 100$，然而后面两个部分分真的m可以开到很大。
题解
显然手环2亮度减c和手环1亮度+c是等价的，所以修改相当于在手环2亮度+c$(|c| \le m)$（显然）
假设下标从0开始到n-1(原题为从1到n)
30pts：枚举移动的位数，和c（$O(n^2m)$）。
70pts：枚举移动的位数，移动过去后变成了一个求$\sum_{i=0}^{n-1}(s_i-c)^2$的最小值，其中$s_i=x_i-y_i$。
然后展开得$nc^2+\sum s_ic+\sum s_i^2$
然后就是求二次方程最小值，时间复杂度$O(1)$，总时间复杂度$O(n^2)$
当然还有C2016红太阳 huhao的$O(nm^2)$神奇算法
100pts：
显然$\sum_{i=0}^{n-1}s_i$是一个定值，$\sum_{i=0}^{n-1}s_i^2=\sum_{i=0}^{n-1}(x_i-y_i)^2=\sum_{i=0}^{n-1}(x_i^2+y_i^2-2x_iy_i)$，显然$\sum_{i=0}^{n-1}(x_i^2+y_i^2)$也是定值，为了结果尽量小，显然要$\sum_{i=0}^{n-1}2x_iy_i$尽量大 ，所以就是要求$\sum_{i=0}^{n-1}x_iy_i$的最大值。
设经过旋转，$x_0$转到了原来$x_k$的位置。
那么就变为$\sum_{i=0}^{n-k-1}x_{i+k}y_i+\sum_{i=0}^{k-1}x_iy_{n-k+i}$
设$x'$为x翻转后的序列，$y'$为y翻转后的序列。
则$\sum_{i=0}^{n-k-1}x_{i+k}y_i+\sum_{i=0}^{k-1}x_iy_{n-k+i}=\sum_{i=0}^{n-k-1}x'_{(n-k-1)-i}y_i+\sum_{i=0}^{k-1}x_iy'_{(k-1)-i}$
设$s=x'\times y$，$s’=x\times y'$则$\sum_{i=0}^{n-k-1}x_{i+k}y_i+\sum_{i=0}^{k-1}x_iy_{n-k+i}=s_{n-k-1}+s'_{k-1}$，就是FFT卷积取最小值。。
然后得到最小值后直接解方程就好，时间复杂度$O(n \log n)$
/*
Author: CNYALI_LK
LANG: C++
PROG: 3723.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
template<class T>T read(){
T s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
// printf("%d\n",a);
int cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;a=-a;}
do{WriteIntBuffer[++cnt]=(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
putchar(end);
}
struct fs{
double x,y;
fs(double a=0.0,double b=0.0){x=a;y=b;}
fs operator +(fs b){return fs(x+b.x,y+b.y);}
fs operator -(fs b){return fs(x-b.x,y-b.y);}
fs operator *(fs b){return fs(x*b.x-y*b.y,x*b.y+y*b.x);}
fs operator /(double b){return fs(x/b,y/b);}
};
fs x[1<<17],y[1<<17],xr[1<<17],yr[1<<17],s1[1<<17],s2[1<<17];
int rev[1<<17];
int f(int x,int a,int b,int c){return x*(x*a+b)+c;}
void FFT(fs *a,int siz,int flg){
for(int i=0;i<siz;++i)if(i>rev[i])swap(a[i],a[rev[i]]);
for(int s=2;s<=siz;s<<=1){
int g=s>>1;
fs ww(cos(pi/g),flg*sin(pi/g));
for(int l=0;l<siz;l+=s){
fs w(1,0);
for(int i=0;i<g;++i){
fs u=a[l+i],v=a[l+i+g]*w;
a[l+i]=u+v;
a[l+i+g]=u-v;
w=w*ww;
}
}
}
if(flg<0)for(int i=0;i<siz;++i)a[i]=a[i]/siz;
}
int main(){
#ifdef cnyali_lk
freopen("3723.in","r",stdin);
freopen("3723.out","w",stdout);
#endif
int n,cnt=0,ccnt=0,ax,ay,M;
n=read<int>();M=read<int>();
for(int i=0;i<n;++i){
ax=read<int>();
x[i]=fs(ax);
xr[n-i-1]=x[i];;
cnt-=ax;
ccnt+=ax*ax;
}
for(int i=0;i<n;++i){
ay=read<int>();
y[i]=fs(ay);
yr[n-i-1]=y[i];;
cnt+=ay;
ccnt+=ay*ay;
}
cnt<<=1;
int m=n+n,s=1,t=0;
while(s<=m){s<<=1;++t;}
for(int i=0;i<s;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(t-1));
FFT(x,s,1);
FFT(y,s,1);
FFT(xr,s,1);
FFT(yr,s,1);
for(int i=0;i<s;++i)s1[i]=x[i]*yr[i];
for(int i=0;i<s;++i)s2[i]=y[i]*xr[i];
FFT(s1,s,-1);
FFT(s2,s,-1);
int ans=(int)(s2[n-1].x+0.5),Ans=0x3f3f3f3f;
for(int k=1;k<n;++k)chkmax(ans,(int)(s2[n-k-1].x+s1[k-1].x+0.5));
ccnt-=ans+ans;
// printf("%d_%d,%d,%d\n",ans,n,cnt,ccnt);
double x=-(cnt/2)*1./n;
/// write(f(-1,n,cnt,ccnt),'\n');
// printf("%lf\n",x);
write(min(f(floor(x),n,cnt,ccnt),f(ceil(x),n,cnt,ccnt)),'\n');
return 0;
}