单调队列优化的上课例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20010,M = 210;
int n,m,dp[M][N];
deque<int> q;
struct Carpenter{
	int l,p,s;
}w[M];
bool cmp(Carpenter x,Carpenter y){
	return x.s<y.s;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i].l>>w[i].p>>w[i].s;
	}
	sort(w+1,w+1+m,cmp);
	for(int i=1;i<=m;i++){
		q.clear();
		for(int j=0;j<=n;j++){
//			q.push_back(0);
			dp[i][j]=dp[i-1][j];
			if(j) dp[i][j]=max(dp[i][j],dp[i][j-1]);
			int l = w[i].l,s = w[i].s,p = w[i].p;
			if(!q.empty()&&q.front()<j-l) q.pop_front();
			if(!q.empty()&&j>=s){
				dp[i][j]=max(dp[i][j],dp[i-1][q.front()]+(j-q.front())*p);
			}
			if(j<s){
				while(!q.empty()&&dp[i-1][q.front()]-q.front()*p<=dp[i-1][j]-j*p) q.pop_back();
				q.push_back(j);
			}
		}
	}
	cout<<dp[m][n];
	return 0;
}