题面

题解

显然两个手环只需要一个的亮度增加\(c \in [-m, m]\)和原题是等价的。

于是可以写成这样一个公式：

于是最后只有\(-2\sum_{i=1}^n x_iy_{i+k}\)不是常数项（假设\(c\)是常数）

于是现在问题变成了求\(\sum_{i=1}^nx_iy_{i+k}\)的最大值。

这个时候就需要用到一些套路。

我们将序列\(y\)反过来然后在后面接一遍，变成多项式卷积。

然后我们可以看出\(\sum x_iy_{i+k}\)就是\(x^{n+k-1}\)的系数，

然后\(\because m \leq 100\)，暴力枚举\(c\)即可。

代码

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define RG register

#define clear(x, y) memset(x, y, sizeof(x));

using namespace std;

inline int read()

{

	int data=0, w=1;

	char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') w=-1, ch=getchar();

	while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();

	return data*w;

}

const int maxn(2000010);

const double pi(acos(-1));

int d[maxn];

int s[maxn], ans=2147483647, cnt;

int n, m, r[maxn], N, M, c[maxn];

complex<double> a[maxn], b[maxn];

template<int opt>

inline void FFT(complex<double> *p)

{

	for(RG int i=0;i<N;i++) if(i<r[i]) swap(p[i], p[r[i]]);

	for(RG int i=1;i<=N;i<<=1)

	{

		RG complex<double> rot(cos(pi/i), opt*sin(pi/i));

		for(RG int j=0;j<N;j+=(i<<1))

		{

			RG complex<double> w(1, 0);

			for(RG int k=0;k<i;k++, w*=rot)

			{

				complex<double> x=p[j+k], y=w*p[j+k+i];

				p[j+k]=x+y; p[j+k+i]=x-y;

			}

		}

	}

}

inline void init()

{

	M=n+(N=n-1);

	for(RG int i=1;i<=n;i++) a[i-1]=d[i];

	for(RG int i=0;i<n;i++) b[i]=b[i+n]=c[n-i];

	M+=N; for(N=1;N<=M;N<<=1) ++cnt;

	for(RG int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1));

	FFT<1>(a); FFT<1>(b); for(RG int i=0;i<N;i++) a[i]*=b[i];

	FFT<-1>(a);

	for(RG int i=0;i<=M;i++) s[i]=(int)(a[i].real()/N+0.5);

}

int main()

{

	n=read(); m=read();

	for(RG int i=1;i<=n;i++) d[i]=read();

	for(RG int i=1;i<=n;i++) c[i]=read();

	init();

	int o=0, p=0, q=0, r=0, maxs=-ans;

	for(RG int i=1;i<=n;i++) o+=d[i]*d[i], p+=c[i]*c[i], q+=d[i], r+=c[i];

	for(RG int i=n-1;i<(n<<1);i++) maxs=max(maxs, s[i]);

	for(RG int C=-m;C<=m;C++)

	{

		int res=o+p+C*C*n+2*C*(q-r)-(maxs << 1);

		ans=min(res, ans);

	}

	printf("%d\n", ans);

	return 0;

}