# 不看题解我不会

## 方案一:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef struct peop
{
int s,p,l;
}people;

people po[101];
int f[101][16001];
int n,k;

struct Data
{
int val,pos;
bool operator<(const Data &ne)const
{
if(val!=ne.val)
return val<ne.val;
else
return pos>ne.pos;
}
Data(){}
Data(int _val,int _pos){val=_val;pos=_pos;}
}temp[16002];

bool cmp(people a,people b)
{
return a.s<b.s;
}

void input()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)scanf("%d%d%d",&po[i].l,&po[i].p,&po[i].s);
sort(po+1,po+k+1,cmp);
}

pair<int,int> q[16001];

void work()
{
for(int i=1;i<=k;i++)
{
priority_queue<Data> q;
for(int j=max(0,po[i].s-po[i].l);j<po[i].s;j++)q.push(Data(f[i-1][j]-po[i].p*j,j));
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(j<po[i].s||j-po[i].l>=po[i].s)continue;
while(!q.empty()&&q.top().pos+po[i].l<j)q.pop();
if(!q.empty())f[i][j]=max(f[i][j],q.top().val+po[i].p*j);
}
}
cout<<f[k][n]<<endl;
}

int main()
{
input();
work();
return 0;
}

## 方法 2:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef struct peop
{
int s,p,l;
}people;

people po[101];
int f[101][16001];
int n,k;

struct Data
{
int val,pos;
Data(){}
Data(int _val,int _pos){val=_val;pos=_pos;}
}q[16002];

bool cmp(people a,people b)
{
return a.s<b.s;
}

void input()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)scanf("%d%d%d",&po[i].l,&po[i].p,&po[i].s);
sort(po+1,po+k+1,cmp);
}

void work()
{
int h,t;
for(int i=1;i<=k;i++)
{
h=0,t=1;
for(int j=max(0,po[i].s-po[i].l);j<po[i].s;j++)
{
int tmp=f[i-1][j]-po[i].p*j;
while(h>=t&&q[h].val<tmp)h--;
q[++h]=Data(tmp,j);
}
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(j<po[i].s||j-po[i].l>=po[i].s)continue;
while(h>=t&&q[t].pos+po[i].l<j)t++;
if(h>=t)f[i][j]=max(f[i][j],q[t].val+po[i].p*j);
}
}
printf("%d\n",f[k][n]);
}

int main()
{
input();
work();
return 0;
}