35pts求调
查看原帖
35pts求调
178992
Hanghang楼主2021/3/28 08:01
#include<bits/stdc++.h>
using namespace std;

long long n,a[1003][1003],b[1003][1003],c[1003],s,S;
int main()
{
	//freopen("pacman.in","r",stdin);
	//freopen("pacman.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)
	{
		c[1]+=a[i][i];c[n]+=a[i][n-i+1];//cout<<c[n]<<endl;
	}
	//cout<<c[1]<<" "<<c[n]<<endl;
	for(int i=2;i<n;i++)
	{
		int k=i;
		for(int j=1;j<=n;j++,k++)c[i]+=a[k][j]+a[j][k];
		k=i-1;int p=2;//cout<<k<<endl;//cout<<c[i]<<endl;
		for(int j=k;j>1;j--,p++)c[i]+=a[j][p]+a[n-j+1][n-p+1];
		//cout<<c[i]<<endl;
	}
    s=c[1];//cout<<s<<" "<<s+c[3];
	for(int i=3;i<=n;i+=2)
	{
		int x=(i-1)/2+1;int y=n-x+1;//cout<<x<<" "<<y<<endl; 
		if(s+c[i]-a[x][x]-a[y][y]>S)S=s+c[i]-a[x][x]-a[y][y];
	}
	//cout<<S<<endl;
	for(int i=2;i<=n;i+=2)if(s+c[i]>S)S=s+c[i];
	s=c[n];
	for(int i=n-2;i>0;i-=2)
	{
		int x=(n-i)/2+1;int y=n-x+1;
		if(s+c[i]-a[x][x]-a[y][y]>S)S=s+c[i]-a[x][x]-a[y][y];
	}
	for(int i=n-1;i>0;i--)if(s+c[i]>S)S=s+c[i];
	for(int i=2;i<n;i++)
	{
	    s=c[i];
	    for(int j=i+2;j<n;j+=2)
	    {
	    	int x=(j-i)/2+1,y=(j+i)/2;
	    	int z=n-x+1,w=n-y+1;
	    	if(s+c[j]-a[x][y]-a[y][x]-a[z][y]-a[y][z]>S)
	    	{
	    		S=s+c[j]-a[x][y]-a[y][x]-a[z][w]-a[w][z];
			}
		}
		for(int j=i+1;j<n;j+=2)if(s+c[j]>S)S=s+c[j];
	}
	cout<<S<<endl;
	return 0;
}
2021/3/28 08:01
加载中...