下面是我用两个单调队列做的，一个维护[j - t, j]的最大值，另一个维护[j + 1, j + t]的最大值，然后转移的时候再取两个队列队头元素的最大值。但是为什么只有10pt呢？

#include <iostream>
#include <cstdio>

using namespace std;

int read(){
	int s = 0;
	char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
	return s;
}

const int N = 4e3 + 5;

int n = read(), m = read(), k = read(), T = read(), a[N][N], dp[N][N];
int front1[N], rear1[N], front2[N], rear2[N], q1[N], q2[N], maxn;

int main(){
	for(int i = 1; i <= k; i++){
		int x = read(), y = read(), v = read();
		a[x][y] = v;
	}
	for(int i = 1; i <= m; i++) dp[1][i] = a[1][i];
	for(int i = 2; i <= n; i++){
		front1[i] = front2[i] = 1;
		for(int j = 1; j <= 1 + T; j++){
			while(front2[i] <= rear2[i] && dp[i - 1][j] >= dp[i - 1][rear2[i]]) rear2[i]--;
			q2[++rear2[i]] = j;
		}
		for(int j = 1; j <= m; j++){
			while(front1[i] <= rear1[i] && q1[front1[i]] < j - T) front1[i]++;
			while(front2[i] <= rear2[i] && q2[front2[i]] < j) front2[i]++;
			dp[i][j] = max(dp[i - 1][q1[front1[i]]], dp[i - 1][q2[front2[i]]]) + a[i][j];
			while(front1[i] <= rear1[i] && dp[i - 1][j] >= dp[i - 1][q1[rear1[i]]]) rear1[i]--;
			q1[++rear1[i]] = j;
			while(front2[i] <= rear2[i] && dp[i - 1][j + T + 1] >= dp[i - 1][q2[rear2[i]]]) rear2[i]--;
			q2[++rear2[i]] = j + T + 1;
		}
	}
	for(int i = 1; i <= m; i++) maxn = max(maxn, dp[n][i]);
	cout << maxn;
	return 0;
}

一个单调队列：

#include <iostream>
#include <cstdio>

using namespace std;

int read(){
	int s = 0;
	char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
	return s;
}

const int N = 4e3 + 5;

int n = read(), m = read(), k = read(), T = read(), a[N][N], dp[N][N];
int front, rear, q[N], maxn;

int main(){
	for(int i = 1; i <= k; i++){
		int x = read(), y = read(), v = read();
		a[x][y] = v;
	}
	for(int i = 1; i <= m; i++) dp[1][i] = a[1][i];
	for(int i = 2; i <= n; i++){
		front = 1, rear = 0;
		for(int j = 1; j <= T; j++){
			while(front <= rear && dp[i - 1][j] >= dp[i - 1][q[rear]]) rear--;
			q[++rear] = j;
		}
		for(int j = 1; j <= m; j++){
			while(front <= rear && q[front] < j - T) front++;
			if(j + T <= m){
				while(front <= rear && dp[i - 1][j + T] >= dp[i - 1][q[rear]]) rear--;
				q[++rear] = j + T;
			}
			dp[i][j] = dp[i - 1][q[front]] + a[i][j];
		}
	}
	for(int i = 1; i <= m; i++) maxn = max(maxn, dp[n][i]);
	cout << maxn;
	return 0;
}```