时光机TimeMachine

对于100%的数据，0<=W<T<=2000,1<=MaxP<=2000

对于所有的数据，1<=BP_i<=AP_i<=1000,1<=AS_i,BS_i<=MaxP

#include<cstdio>
#include<cstdlib>
#include<deque>
#include<algorithm>
using namespace std;
const int N = 2200;
const int MAX = 2.1E9;
int n,m,w,buy[N][2],lim[N][2],f[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
int dui[N],dl,dr,pos[N];
int main(){
	int i,j;
	//freopen("in.txt","r",stdin);
	n=scan();m=scan();w=scan();
	for(i=1;i<=n;i++){
		scanf("%d%d%d%d",&buy[i][0],&buy[i][1],&lim[i][0],&lim[i][1]);
	}
	for(i=1;i<=n;i++)
	for(j=0;j<=m;j++){
		if(j<=lim[i][0])f[i][j] = -j*buy[i][0];
		else f[i][j]=-MAX;
	}
	
	for(i=2;i<=n;i++){
		for(j=0;j<=m;j++)
			f[i][j] = max(f[i][j],f[i-1][j]);
		int i2=i-w-1;
		if(i2<=0)continue;
		//buy
		dl=1;dr=0;
		for(j=0;j<=m;j++){
			//pop front
			while(dl<=dr && j-pos[dl] > lim[i][0])dl++;
			if(dl<=dr)f[i][j] = max(f[i][j],dui[dl]-j*buy[i][0]);
			//push now
			int val = f[i2][j]+j*buy[i][0];
			while(dl<=dr && dui[dr]<=val)dr--;
			dr++;
			dui[dr] = val;
			pos[dr] = j;
		}
		
		//sell
		dl=1;dr=0;
		for(j=m;j>=0;j--){
			//pop front
			while(dl<=dr && pos[dl]-j > lim[i][1])dl++;
			if(dl<=dr)f[i][j] = max(f[i][j],dui[dl]-j*buy[i][1]);
			//push now
			int val = f[i2][j]+j*buy[i][1];
			while(dl<=dr && dui[dr]<=val)dr--;
			dr++;
			dui[dr] = val;
			pos[dr] = j;
		}
	}
	printf("%d\n",f[n][0]);
	return 0;
}