记录编号	601505	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1841.[国家集训队2011]免费的馅饼(加强版)	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.705 s
提交时间	2025-06-25 16:17:48	内存使用	3.93 MiB

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100005;

int w,n;
struct node{
    int t,p,v;
}b[MAXN];
long long dp[MAXN],ans = 0;
bool cmp(node x,node y){
    return x.t < y.t;
}

int main(){
	freopen("free.in","r",stdin);
	freopen("free.out","w",stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> w >> n;
    for(int i = 1;i <= n;i ++){
        cin >> b[i].t >> b[i].p >> b[i].v;
    }
    sort(b + 1,b + n + 1,cmp);
    for(int i = 1;i <= n;i ++){
        dp[i] = b[i].v;
        for(int j = 1;j < min(1000,i);j ++){
            if(2 * abs(b[i].t - b[i - j].t) >= abs(b[i].p - b[i - j].p)){
                dp[i] = max(dp[i],dp[i - j] + b[i].v);
            }
        }
    }
    for(int i = 1;i <= n;i ++){
        ans = max(ans,dp[i]);
    }
    cout << ans << '\n';
	return 0;
}