用了Dinic>_<。前两个点跑了1.2s

#include<cstdio>
#include<cstring>
#define ll long long
const int INF=(1ll<<31)-1;
const int E=5e4+10,V=4e3+10;
struct networkflow
{
	int nx[E],ls[V],to[E],cap[E],cst[E],tot=1;
	void addedge(int u,int v,int capacity,int cost)
	{
		nx[++tot]=ls[u];
		to[ls[u]=tot]=v;
		cap[tot]=capacity;
		cst[tot]=cost;
	}
	void add(int u,int v,int capacity,int cost)
	{
		addedge(u,v,capacity,cost);
		addedge(v,u,0,-cost);
	}
	int dis[V],q[V],cur[V];
	bool vis[V];
	bool SPFA(int s,int t)
	{
		memset(dis,0x3f,sizeof dis);
		memcpy(cur,ls,sizeof cur);
		int head=0,tail=1;
		dis[q[1]=s]=0;
		while(head<tail)
		{
			int u=q[++head];vis[u]=0;
//			printf("bfs %d\n",u);
			for(int i=ls[u];i;i=nx[i])
			if(cap[i]&&dis[to[i]]>dis[u]+cst[i])
			{
				dis[to[i]]=dis[u]+cst[i];
				if(!vis[to[i]])
				vis[q[++tail]=to[i]]=1;
			}
		}
		return dis[t]!=dis[0];
	}
	ll min(ll a,ll b) {return a<b?a:b;}
	ll mincost;
	ll dfs(int u,int t,ll flow=INF)
	{
//		printf("dfs %d\n",u);
		if(u==t) return flow;
		ll ret=0;vis[u]=1;
		for(int &i=cur[u];i&&flow;i=nx[i])
		if(!vis[to[i]]&&cap[i]&&dis[to[i]]==dis[u]+cst[i])
		{
			ll f=dfs(to[i],t,min(flow,cap[i]));
			ret+=f;flow-=f;cap[i]-=f;cap[i^1]+=f;
			mincost+=f*cst[i];
		}
		vis[u]=0;
		return ret;
	}
	ll dinic(int s,int t)
	{
		ll ret=0;
		while(SPFA(s,t))
		ret+=dfs(s,t);
		return ret;
	}
}F,tmp;
int m;
int f1(int x,int y) {return (2*m-2+x)*(x-1)+2*y-1;}
int f2(int x,int y) {return f1(x,y)+1;}
const int N=1e3;
int a[N][N];
int main()
{
	int n;scanf("%d%d",&m,&n);
	int s=f2(n,n+m-1)+1,t=s+1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i+m-1;j++)
	{
		scanf("%d",&a[i][j]);
		if(i==1) F.add(s,f1(i,j),1,0);else{
		if(j<i+m-1) F.add(f2(i-1,j),f1(i,j),1,0);
		if(j>1) F.add(f2(i-1,j-1),f1(i,j),1,0);}
		F.add(f1(i,j),f2(i,j),1,-a[i][j]);
		if(i==n) F.add(f2(i,j),t,1,0);
	}
	tmp=F;F.dinic(s,t);
	printf("%d\n",-F.mincost);
	F=tmp;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i+m-1;j++)
	{
		F.add(f1(i,j),f2(i,j),INF,-a[i][j]);
		if(i==n) F.add(f2(i,j),t,INF,0);
	}
	tmp=F;F.dinic(s,t);
	printf("%d\n",-F.mincost);
	F=tmp;
	for(int i=2;i<=n;i++)
	for(int j=1;j<=i+m-1;j++)
	{
		if(j<i+m-1) F.add(f2(i-1,j),f1(i,j),INF,0);
		if(j>1) F.add(f2(i-1,j-1),f1(i,j),INF,0);
	}
	F.dinic(s,t);
	printf("%d\n",-F.mincost);
}