题目传送门
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int>PA;
const int maxn=16000+10;
const int maxk=100+10;
int k,n;
int dp[maxk][maxn];
struct People{
int L,P,S;
bool operator <(const People &A)const
{
return S<A.S;
}
}peo[maxk];
int main()
{
while(scanf("%d%d",&n,&k)==2)
{
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&peo[i].L,&peo[i].P,&peo[i].S);
}
sort(peo+1,peo+k+1);
memset(dp,0,sizeof(dp));
for(int i=1;i<=k;i++)
{
int L=peo[i].L,P=peo[i].P,S=peo[i].S;
priority_queue<PA,vector<PA>,less<PA> >que;
for(int j=max(0,S-L);j<S;j++)
que.push(PA(dp[i-1][j]-j*P,j));
for(int j=1;j<=n;j++)
{
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
if(S>j||S+L-1<j)
continue;
PA p=que.top();
while(!que.empty()&&p.second+L<j)
{
que.pop();
p=que.top();
}
if(que.empty())
continue;
dp[i][j]=max(dp[i][j],p.first+j*P);
}
}
printf("%d\n",dp[k][n]);
}
}