RT

这份代码居然只有50pts，比暴力都还低

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

const int N=5505;
int n,w,s;
long long ans=-1e18;
int a[N];
long long f[N][N];

int main(void)
{
	scanf("%d%d%d",&n,&w,&s);
	for(register int i=1;i<=n;++i)
		scanf("%d",a+i);
	for(register int i=0;i<=n;++i)
		for(register int j=0;j<=w;++j)
			f[i][j]=-1e18;
	f[0][0]=0;
	for(register int i=1;i<=n;++i)
	{
		deque<int>q;
		q.push_front(w);
		for(register int j=w;j;--j)
		{
			while(q.front()>j+s-1&&!q.empty()) q.pop_front();
			while(f[i-1][q.back()]<f[i-1][j-1]&&!q.empty()) q.pop_back();
			q.push_back(j-1);
			f[i][j]=f[i-1][q.front()]+1ll*a[i]*j;
		}
	}
	for(register int i=1;i<=w;++i)
		ans=max(ans,f[n][i]);
	printf("%lld\n",ans);
	return 0;
}

换成手写队列就A了