mark~~

 

 1 //#include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<stack>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<cstring>
 8 #define mem(a) memset(a,0,sizeof(a))
 9 #define ll long long
10 #define mp make_pair
11 #define pb push_back
12 #define inf 0x3f3f3f3f
13 using namespace std;
14 const int N=16000+5;
15 int n,maxp,k;
16 int l[N],p[N],s[N],dp[N][N],x[N],y[N],st[N];
17 struct node
18 {
19     int l,p,s;
20 }a[150];
21 int cmp(node a,node b)
22 {
23     return a.s<b.s;
24 }
25 void solve()
26 {
27    sort(a+1,a+k+1,cmp);
28    for(int i=1;i<=k;i++)
29    {
30        x[i]=max(0,a[i].s-a[i].l);  //左右边界
31        y[i]=min(n,a[i].s+a[i].l-1);
32    }
33    for(int i=1;i<=k;i++)
34    {
35       for(int j=0;j<=y[i];j++)
36         dp[i][j]=dp[i-1][j];
37       int be=1,ed=1;
38       for(int j=x[i];j<a[i].s;j++)
39       {
40           while(be<ed&&dp[i-1][j]-j*a[i].p>=dp[i-1][st[ed]]-st[ed]*a[i].p) ed--;
41           st[++ed]=j;
42       }
43       for(int j=a[i].s;j<=y[i];j++)
44       {
45           while(be<ed&&j-st[be]>a[i].l) be++;
46           dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
47           dp[i][j]=max(dp[i][j],dp[i-1][st[be]]+(j-st[be])*a[i].p);
48       }
49       for(int j=y[i]+1;j<=n;j++)
50           dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
51    }
52    int ans=0;
53    for(int i=1;i<=n;i++)
54         ans=max(ans,dp[k][i]);
55    printf("%d\n",ans);
56 }
57 int main()
58 {
59     scanf("%d%d",&n,&k);
60     for(int i=1;i<=k;i++)
61        scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);
62     solve();
63 
64     return 0;
65 }
66 /*
67 dp[i][j]=max{dp[i-1][j],dp[i][j-1],dp[i-1][k]+(j-k)*p[i]}
68 
69 */

(⊙x⊙;)