维护了一个上凸壳

#include<bits/stdc++.h>
#define MAXN 200005
#define MAXM 1005
#define int long long
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
using namespace std;

inline int read(){
    int x=0;
    int f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

bool M1;
int n,m;
struct node{
	int x,y;
};
int w[MAXM][MAXM];
deque<node> q;
int pos[MAXM],dis[MAXM],f[MAXM][MAXM];
const int inf=1e9;
const double eps=1e-6;

double get_k(node aa,node bb){
	return 1.0*(bb.y-aa.y)/((aa.x==bb.x)?eps:(bb.x-aa.x));
}

bool M2;

signed main(){
//  freopen("","r",stdin);
//  freopen("","w",stdout);
    int Time=clock();
	n=read();m=read();
	for(int i=1;i<=n;i++){
		int x,y;
		x=read();y=read();
		w[x][y]=read();
	}
	memset(f,-0x3f,sizeof(f));
	f[1][1]=w[1][1];
	pos[1]=1;
	for(int i=1;i<=m;i++){
		q.clear();
		for(int j=1;j<=m;j++){
			if(pos[j]) dis[j]=(i-pos[j])*(i-pos[j]);
			else dis[j]=0;
		}
		for(int j=1;j<=m;j++){
			if(pos[j]){
				node tmp={j,f[pos[j]][j]-dis[j]-j*j};
				while(q.size()>=2 && get_k(q[q.size()-2],tmp)>=get_k(q[q.size()-2],q.back())) q.pop_back();
				q.push_back(tmp);
			}
			if(w[i][j] && (i>1&&j>1)){
				while(q.size()>=2 && -2*j<=get_k(q[0],q[1])) q.pop_front();
				int x=q.front().x,y=q.front().y;
//				printf("i=%d j=%d x=%d\n",i,j,x);
				f[i][j]=w[i][j]-j*j+2*j*x+y;
				pos[j]=i;
				dis[j]=0;
				node tmp={j,f[pos[j]][j]-dis[j]-j*j};
				while(q.size()>=2 && get_k(q[q.size()-2],tmp)>=get_k(q[q.size()-2],q.back())) q.pop_back();
				q.push_back(tmp);
			}
		}
	}
	int ans=f[m][m];
	printf("%lld\n",ans);
    look_memory;
    look_time;
    return 0;
}