记录编号	460035	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	自动ac机	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.460 s
提交时间	2017-10-16 14:24:07	内存使用	53.70 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int n,k,tot,w[maxn],c[maxn],bug[maxn],pri[maxn],mark[maxn];
long long f[maxn],p[maxn],s[maxn];
struct poi{
	long long k;
	int num;
}q[maxn];
bool cmp(int x,int y){return bug[x]<bug[y];}
void GetPrime(){
	for(int i=2;i<=maxn;i++){
		if(!mark[i])pri[++tot]=i;
		for(int j=1;j<=tot&&pri[j]*i<=maxn;j++){
			mark[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}
}
void Getmax(){//单调队列
	int l=1,r=1;
	for(int i=1;i<=k;i++){
		f[i]=q[l].k+s[i]*s[i];
		while(q[r].k<=f[i]-s[i]*s[i]-p[i]*p[i]&&r>=l)r--;
		q[++r].k=f[i]-s[i]*s[i]-p[i]*p[i];
		q[r].num=i;
	}
	for(int i=k;i<=n;i++){
		f[i]=q[l].k+s[i]*s[i];
		while(q[r].k<=f[i]-s[i]*s[i]-p[i]*p[i]&&r>=l)r--;
		q[++r].k=f[i]-s[i]*s[i]-p[i]*p[i];
		q[r].num=i;
		while(q[l].num<=i-k)l++;
	}
}
int main(){
	freopen("acauto.in","r",stdin);
	freopen("acauto.out","w",stdout);
	scanf("%d%d",&n,&k);
	GetPrime();
	for(int i=1;i<=n;i++)scanf("%d",&w[i]),s[i]=s[i-1]+w[i];
	for(int i=1;i<=n;i++)scanf("%d",&bug[i]),c[i]=i;
	sort(c+1,c+1+n,cmp);
	int d,head=1;
	for(int i=1;i<=n;i++){
		d=c[i];
		while(bug[d]>=pri[head])head++;
		p[d]=pri[head-1];
	}
	Getmax();
	printf("%lld\n",f[n]);
	return 0;
}