垃圾陷阱

#include<bits/stdc++.h>
using namespace std;
int D,G,sum;
int dp[105][1005];
struct garbage
{
	int t,f,h;
}a[105];
bool cmp(garbage x,garbage y)
{
	return x.t<y.t;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	memset(dp,-1,sizeof dp);
	cin>>D>>G;
	for(int i=1; i<=G; i++)
		cin>>a[i].t>>a[i].f>>a[i].h;
	sort(a+1,a+1+G,cmp);
	dp[0][0]=10;
	a[0].t=a[0].f=a[0].h=0;
	for(int i=0; i<G; i++)
		for(int j=0; j<=D; j++)
		{	
			if(dp[i][j]<0)continue;
			if(j+a[i+1].h>=D&&dp[i][j]>=a[i+1].t-a[i].t){cout<<a[i+1].t;return 0;}
			if(dp[i][j]>=a[i+1].t-a[i].t)dp[i+1][j+a[i+1].h]=dp[i][j]-a[i+1].t+a[i].t;
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]-a[i+1].t+a[i].t+a[i+1].f);
		}
	int hp=10,ans=0;
	for(int i=1; i<=G; i++)
	{
		if(a[i].t-a[i-1].t>hp){cout<<ans+hp;return 0;}
		hp-=a[i].t-a[i-1].t;
		hp+=a[i].f;
		ans+=a[i].t-a[i-1].t;
	}
	cout<<ans+hp;
	return 0;
}

73pts