记录编号	581561	评测结果	AAAAAAAAAA
题目名称	[POJ 1821]粉刷栅栏	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2023-08-05 14:30:37	内存使用	2.66 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 26010,M = 210;
int n,m;
struct made{
    int l,p,s;
}a[M];
int dp[M][N];
deque<int>q;
bool cmp(made x,made y){
    return x.s < y.s; 
}
int vv(int x,int y){
    return dp[x-1][y] - a[x].p * y;
}
int main(){
    freopen("fence_paint.in","r",stdin);
    freopen("fence_paint.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);
    sort(a+1,a+1+m,cmp);
    for(int i = 1;i <= m;i++){
        q.clear();
        for(int k = max(0,a[i].s-a[i].l);k <= a[i].s-1;k++){
            while(q.size() && vv(i,q.back()) <= vv(i,k))q.pop_back();
            q.push_back(k);
        }
        for(int j = 1;j <= n;j++){
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            if(j >= a[i].s){
                while(q.size() && q.front() < j-a[i].l)q.pop_front();
                if(q.size())dp[i][j] = max(dp[i][j],vv(i,q.front())+a[i].p*j);
            }
        }
    }
    printf("%d\n",dp[m][n]);
    
    return 0;
    
}