#include<bits/stdc++.h>
#define N 2005
using namespace std;

int n, m, w, inPri[N], outPri[N], inLim[N], outLim[N];

deque<int> q;
int f[N][N];

int g(int i, int j, bool opt) {
	if(!opt) return f[i-w][j]+j*inPri[i];
	return f[i-w][j]+j*outPri[i];
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> w;
	++w;
	for(int i=1; i<=n; ++i)
		cin >> inPri[i] >> outPri[i] >> inLim[i] >> outLim[i];
	
	memset(f, 128, sizeof f);
	
	for(int i=1; i<=n; ++i) {
		for(int j=0; j<=inLim[i]; ++j)
			f[i][j]=-inPri[i]*j;
		for(int j=0; j<=m; ++j)
			f[i][j]=max(f[i][j], f[i-1][j]);
		if(i<=w+1) continue;
		q.clear();
		for(int j=0; j<=m; ++j) {
			while(q.size() && j-q.front()>inLim[i])
				q.pop_front();
			while(q.size() && g(i, q.back(), 0)<g(i, j, 0))
				q.pop_back();
			q.push_back(j);
			if(q.size()) f[i][j]=max(f[i][j], g(i, q.front(), 0)-j*inPri[i]);
		}
		
		q.clear();
		for(int j=m; ~j; --j) {
			while(q.size() && q.front()-j>outLim[i])
				q.pop_front();
			while(q.size() && g(i, q.back(), 1)<g(i, j, 1))
				q.pop_back();
			q.push_back(j);
			if(q.size()) f[i][j]=max(f[i][j], g(i, q.front(), 1)-j*outPri[i]);
		}
	}
	
	int ans=0;
	for(int i=0; i<=m; ++i)
		ans=max(ans, f[n][i]);
	cout << ans << '\n';
	return 0;
}

WA #7 #10

打开题解一看简直和第一篇题解的写法一模一样.

哪位大佬帮我看看QwQ