AT_abc266_d [ABC266D] Snuke Panic (1D)（dp）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,ll>PII;
const int N=1e5+10,M=5;
vector<PII>event(N);
ll n,m,t,x,a,ans=0;
ll dp[N][M];
int w[N][M];
int main() {
	cin>>n;
	
	memset(dp,-0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>t>>x>>a;
	event[t]={x,a};
		ans=max(ans,t);
	}
	
	for(int i=1;i<=ans;i++)
	{
		for(int j=0;j<5;j++)
		{
			ll cnt=-0x3f;
			for(int k=max(0,j-1);k<=min(4,j+1);k++)
			{				
				dp[i][j]=max(dp[i][j],dp[i-1][k]);
			}
		}
		
		if(event[i].first!=-1)
		{
			int x=event[i].first;
			ll a=event[i].second;
			if(dp[i][x]!=-0x3f)dp[i][x]+=a;
		}
		
	}
	ll ans=-0x3f;
	for(int j=0;j<=4;j++)
	{
		ans=max(ans,dp[t][j]);
	}
	cout<<ans<<endl;
}