85pts求调
查看原帖
85pts求调
174806
xbb2楼主2021/3/28 08:23
#include<bits/stdc++.h>
using namespace std;
long long a[3005][3005];
long long f[100005];
int main(){
	//freopen("pacman.in","r",stdin);
	//freopen("pacman.out","w",stdout);
	//rp++
	int n;
	cin>>n;
	for(int i=0;i<=2*n+1;i++){
		for(int j=0;j<=2*n+1;j++){
			a[i][j]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	for(int i=1;i<=2*n-2;i++){
		for(int j=1;j<=2*n-2;j++){
			int xx=i;
			int yy=j;
			if(i>n){
				xx=2*n-i;
			}
			if(j>n){
				yy=2*n-j;
			}
			a[i][j]=a[xx][yy];
		}
	}
	/*for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++){
			printf("%3d",a[i][j]);
		}
		printf("\n");
	}*/
	int x=1;
	int y=1;
	while(a[x][y]!=-1&&x<=n&&y<=n){
		f[1]+=a[x][y];
		x++;
		y++;
	}
	x=n;
	y=1;
	while(a[x][y]!=-1&&x>=1&&y>=1){
		f[n]+=a[x][y];
		x--;
		y++;
	}
	for(int i=2;i<=n-1;i++){
		//left
		x=i;
		y=1;
		while(a[x][y]!=-1){
			f[i]+=a[x][y];
			x++;
			y++;
		}
		//right
		x=i;
		y=1;
		while(a[x][y]!=-1){
			f[i]+=a[x][y];
			x--;
			y++;
		}
		f[i]-=a[i][1];
	}
	/*for(int i=1;i<=n;i++){
		printf("%d\n",f[i]);
	}*/
	long long ans=INT_MIN;
	for(int a1=1;a1<=n;a1++){
		for(int b=a1+1;b<=n;b++){
			if((b-a1)%2==0){
				int k=(b-a1)/2;
				long long sum=f[a1]+f[b]-a[1+k][a1+k];
				if(!(a1==1&&b==n)){
					sum-=a[1+k+(n-b)][a1+k+(n-b)];
				}
				ans=max(sum,ans);
			}
			else{
				long long sum=f[a1]+f[b];
				ans=max(sum,ans);
			}
		}
	}
	printf("%lld",ans);
/*4 
20 1 19 2
3 18 4 17
16 5 15 6
7 14 8 13*/
	return 0;
}
2021/3/28 08:23
加载中...