自动搬运

查看原文

来自洛谷，原作者为

	Reunite Wish us good luck.

搬运于2025-08-24 23:10:26，当前版本为作者最后更新于2025-02-28 08:39:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题。

注意到一个 ban 掉的矩形至少会留下一条边界上的两个端点，所以所有的点都至少可以被集中在矩形的两个对角顶点上，先放完仅能放在一个顶点上的，对于能在两个顶点自由选择的点，显然全放在更多的那边更优。

但这样不一定最优，可能存在中间的一个点能够集中很多点。我们直接枚举一个中间点，把所有能放的点全部集中过来，剩下的点继续考虑选择放在对角顶点即可，直接模拟用差分维护一下即可做到 $O(n+XY)$。

正确性的话，稍微画一下能发现最优情况不会选择 $\ge 4$ 个点，且非顶点不会选择超过 $1$ 个，因为非顶点之间也肯定是尽量把一个弄的很大，剩下的那个一定可以平移到顶点上，或者与一个顶点重新分成一对对角顶点。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

int n,X,Y,all;
int A[16];
int a[16][1005][1005];

inline void in(int &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

int main(){
	in(n),in(X),in(Y);
	while(n--){
		int x,y,xx,yy,c,s=0;
		in(x),in(y),in(xx),in(yy),in(c);
		all+=c;
		if(x==1&&y==1) s|=1;
		if(x==1&&yy==Y) s|=2;
		if(xx==X&&y==1) s|=4;
		if(xx==X&&yy==Y) s|=8;
		A[s]+=c;
		a[s][x][y]+=c;
		a[s][xx+1][y]-=c;
		a[s][x][yy+1]-=c;
		a[s][xx+1][yy+1]+=c;
	}
	for(int s=0;s<16;s++)
		for(int i=1;i<=X;i++)
			for(int j=1;j<=Y;j++)
				a[s][i][j]+=a[s][i-1][j]+a[s][i][j-1]-a[s][i-1][j-1];
	ll ans=0;
	for(int x:{0,1,2,3}){
		for(int y:{0,1,2,3}){
			if(x==y) continue;
			ll xx=0,yy=0,cc=0;
			for(int s=0;s<16;s++){
				if(!(s>>x&1)) xx+=A[s];
				if(!(s>>y&1)) yy+=A[s];
				if(!(s>>x&1)&&!(s>>y&1)) cc+=A[s];
			}
			if(xx<yy) xx-=cc;
			else yy-=cc;
			ans=max(ans,xx*(xx-1)/2+yy*(yy-1)/2);
		}
	}
	for(int i=1;i<=X;i++){
		for(int j=1;j<=Y;j++){
            if(i==1&&j==1) continue;
			if(i==1&&j==Y) continue;
			if(i==X&&j==1) continue;
			if(i==X&&j==Y) continue;
			ll s=all;
			for(int x=0;x<16;x++) s-=a[x][i][j];
			s=s*(s-1)/2;
			ans=max(ans,s);
			int b[4]={0},c[4][4]={0};
			for(int x=0;x<16;x++){
				for(int xx:{0,1,2,3}){
					if((x>>xx)&1) continue;
					b[xx]+=a[x][i][j];
					for(int yy:{0,1,2,3})
						if(!((x>>yy)&1)) c[xx][yy]+=a[x][i][j];
				}
			}
			for(int x:{0,1,2,3}){
				ans=max(ans,s+1ll*b[x]*(b[x]-1)/2);
				for(int y:{0,1,2,3}){
					if(y==x) continue;
					ll xx=b[x],yy=b[y];
					if(xx>yy) yy-=c[x][y];
					else xx-=c[x][y];
					ans=max(ans,s+xx*(xx-1)/2+yy*(yy-1)/2);
				}
			}
		}
	}
	printf("%lld\n",ans);

	return 0;
}