rt。record

单调队列优化前 40pts+TLE，优化后30pts+WA。

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

int n,m,k,t;
int val[4005][4005];

int dp[4005][4005];
int ans=-1e9;

//Subtask#1 n<=200
//Subtask#2 n<=4000

deque<int> q;

void update(int i,int j,int l){
	while(q.size()&&q.front()<=j-l) q.pop_front();
	while(q.size()&&dp[i][q.back()]<=dp[i][j]) q.pop_back();
	q.push_back(j);
}

int main(){
	ios::sync_with_stdio(0);
	
	cin>>n>>m>>k>>t;
	
	int x,y,v;
	for(int i=1;i<=k;++i){
		cin>>x>>y>>v;
		val[x][y]=v;
	}
	
	for(int i=1;i<=n;++i){
		q.clear();
		for(int j=1;j<=t;++j) update(i-1,j,2*t+1);
		for(int j=1;j<=m;++j){
			if(j+t<=m) update(i-1,j+t,2*t+1);
			dp[i][j]=dp[i-1][q.front()]+val[i][j];
			if(i==n) ans=max(ans,dp[i][j]);
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}