血 流 成 河

求助……

#include <cstdio>
#include <deque>

const int N = 5005;
int AP[N], BP[N], AS[N], BS[N];
int f[N][N], s[N], s2[N];
inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}

struct Queue {
	std::deque<int> q;
	inline void push(const int x) {
		while (q.size() && s[q.back()] <= s[x]) q.pop_back();
		q.push_back(x);
	}
	inline void pop(const int x) {
		while (q.size() && q.front() < x) q.pop_front();
	}
	inline int front() const {return s[q.front()];}
	inline int size() const {return q.size();}
} q;

struct Queue2 {
	std::deque<int> q;
	inline void push(const int x) {
		while (q.size() && s2[q.back()] <= s2[x]) q.pop_back();
		q.push_back(x);
	}
	inline void pop(const int x) {
		while (q.size() && q.front() < x) q.pop_front();
	}
	inline int front() const {return s2[q.front()];}
	inline int size() const {return q.size();}
} q2;

int main() {
	int T, P, W;
	scanf("%d%d%d", &T, &P, &W);
	for (int i(1); i <= T; ++ i) scanf("%d%d%d%d", AP + i, BP + i, AS + i, BS + i);
	for (int i(1); i <= P; ++ i) f[0][i] = -0x5fffffff;
	for (int i(1); i <= T; ++ i) {
		q.q.clear(), q2.q.clear();
		const int *F(f[max(0, i - W - 1)]);
		int *F2(f[i]);
		for (int j(0); j <= AS[i]; ++ j) f[i][j] = -AP[i] * j;
		for (int j(P); j; -- j) f[i][j] = max(f[i][j], f[i - 1][j]);
		for (int j(0); j <= P; ++ j)
		s[j] = F[j] + j * AP[i], s2[j] = F[j] + j * BP[i];
		for (int j(0); j < BS[i]; ++ j) q2.push(j);
		for (int j(0); j <= P; ++ j) {
			if (j > AS[i]) q.pop(j - AS[i]); q.push(j);
			q2.pop(j); if (j + BS[i] <= P) q2.push(j + BS[i]);
			F2[j] = max(q.front() - j * AP[i], q2.front() - j * BP[i]);
		}
	}
	int ans(-0x7fffffff);
	for (int j(0); j <= P; ++ j) ans = max(ans, f[T][j]);
	printf("%d", ans);
}