常规DP（超时）：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node{LL x,f,c;}a[505];
LL dp[505][10005];//到第 i 个商店，买了 j 吨饲料的最小花费
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    LL k,e,n;cin>>k>>e>>n;
    for(LL i=1;i<=n;i++)cin>>a[i].x>>a[i].f>>a[i].c;
    sort(a+1,a+1+n,[](node x,node y){
        return make_tuple(x.x,x.c,x.f)<make_tuple(y.x,y.c,y.f);
    });
    a[n+1]=node{e,0,0};//新增最后一个商店
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(LL i=1;i<=n+1;i++)
        for(LL j=0;j<=k;j++)
            for(LL x= max(0ll,j-a[i].f); x<=j; x++)//枚举先前有几吨饲料 
                dp[i][j]=min(dp[i][j],
                             dp[i-1][x]+(j-x)*a[i].c+x*x* (a[i].x-a[i-1].x) 
                            );
    cout<<dp[n+1][k];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node{LL x,f,c;}a[505];
LL dp[505][10005];//到第 i 个商店，买了 j 吨饲料的最小花费
LL q[10005];
LL calc(LL i,LL j,LL x) //计算第 i 个商店，买了 j 吨饲料，前一个商店买了 x 吨饲料的花费
{
    return dp[i-1][x]+(j-x)*a[i].c+x*x*(a[i].x-a[i-1].x);
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    LL k,e,n;cin>>k>>e>>n;
    for(LL i=1;i<=n;i++)cin>>a[i].x>>a[i].f>>a[i].c;
    sort(a+1,a+1+n,[](node x,node y){
        return make_tuple(x.x,x.c,x.f)<make_tuple(y.x,y.c,y.f);
    });
    a[n+1]=node{e,0,0};//新增最后一个商店
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(LL i=1;i<=n+1;i++)
    {
        int h=1,t=1;q[1]=0;dp[i][0]=0;
        for(LL j=1;j<=k;j++)
        {
            while(h<=t&&q[h]+a[i].f<=q[t])h++;
            while(h<=t&&calc(i,j,q[t])>=calc(i,j,j))t--;
            q[++t]=j;
            dp[i][j]=calc(i,j,q[h]);
        }
    }
    cout<<dp[n+1][k];
    return 0;
}