单调队列优化DP

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define N 100010
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
typedef long long LL;
using namespace std;
struct node{int X,F,C;};
int cmp(node a,node b){return a.X<b.X;}
node a[N];
LL q1[N],q2[N],x[N],c[N],f[N],dp0[N],dp1[N];
int k,e,n;
int main()
{
  scanf("%d%d%d",&k,&e,&n);
  int i,j;
  FOR(i,1,n)
  {
    scanf("%d%d%d",&a[i].X,&a[i].F,&a[i].C);
  }
  sort(a+1,a+1+n,cmp);
  FOR(i,1,n) f[i]=a[i].F,c[i]=a[i].C,x[i]=a[i].X;
  FOR(i,1,k) dp0[i]=1e15;
  FOR(i,1,f[1]) dp0[i]=c[1]*i;
  dp0[0]=0;
  FOR(i,2,n)
  {
    dp1[0]=0;
    int h=1,t=0;q1[h]=0;
    FOR(j,0,k)
    {
      LL tmp=dp0[j]+(x[i]-x[i-1])*j*j-c[i]*j;
      while (q1[h]<j-f[i]&&h<=t) h++;
      while (h<=t&&q2[t]>tmp) t--;
      t++;q2[t]=tmp;q1[t]=j;dp1[j]=q2[h]+c[i]*j;
    }
    memcpy(dp0,dp1,sizeof(dp0));
  }
  printf("%lld\n",dp0[k]+(e-x[n])*k*k);
}