单调队列优化DP
//状态转移方程：f[i][j]=min(f[i-k][j-1]+(s[i]-s[i-p])*g[j])
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const LL inf=0x3f3f3f3f3f3f3f3f;
LL x[10000+10],s[10000+10],q[10000+10];
LL g[200+10];
LL f[2][10000+10];
int n,k,a,b;
int front,rear;
int main()
{
while(~scanf("%d%d%d%d",&n,&k,&a,&b))
{
int i,j;
LL ave=0;
LL minv=inf;
int loc,amount;
s[0]=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&x[i]);
ave+=x[i];
}
ave/=n;
for(i=1;i<=n;i++)
{
x[i]=(x[i]-ave)*(x[i]-ave);
s[i]=s[i-1]+x[i];
}
for(i=1;i<=k;i++) scanf("%lld",&g[i]);
memset(f,inf,sizeof(f));//memset也很费时间，因为此处，无限TLE,所以将f[210][N]改为f[2][N],又省空间又省时间
f[0][0]=0;
int p;
for(i=1,p=1;i<=k;i++,p=!p)
{
front=rear=0;
memset(f[p],inf,sizeof(f[p]));
for(j=i*a;j<=i*b&&j<=n;j++)
{
while(front<rear&&((f[!p][q[rear-1]]-s[q[rear-1]]*g[i])>=(f[!p][j-a]-s[j-a]*g[i]))) rear--;
//注意是小于等于，由于疏忽了这句“output the smaller T.”，导致无限WA
q[rear++]=j-a;
while(front<rear&&q[front]<(j-b)) front++;
f[p][j]=f[!p][q[front]]+(s[j]-s[q[front]])*g[i];
}
if(f[p][n]<minv)
{
minv=f[p][n];
loc=i;
amount=n-q[front];
}
}
if(minv<inf) printf("%lld %d %d\n",minv,loc,amount);
else printf("No solution.\n");
}
return 0;
}