C11ROOKS - Hai quân xe
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#define MAX 350
int a[MAX][MAX];
int r[MAX];
int c[MAX];
int n,b;
void init(void)
{
int i,j;
scanf("%d",&n);
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
{
scanf("%d",&a[i][j]);
r[i]+=a[i][j];
c[j]+=a[i][j];
}
}
int max(int x,int y)
{
int i,cx,cy,mx,my;
mx=-32000;
my=-32000;
for (i=1;i<=n;i=i+1)
if (c[i]-2*a[x][i]-a[y][i]>mx)
{
mx=c[i]-2*a[x][i]-a[y][i];
cx=i;
}
for (i=1;i<=n;i=i+1)
if (c[i]-2*a[y][i]-a[x][i]>my)
{
my=c[i]-2*a[y][i]-a[x][i];
cy=i;
}
if (cx!=cy) return (mx+my+r[x]+r[y]);
int cx1,cy1,mx1,my1;
mx1=-32000;
my1=-32000;
for (i=1;i<=n;i=i+1)
if ((i!=cx) && (c[i]-2*a[x][i]-a[y][i]>mx1))
{
mx1=c[i]-2*a[x][i]-a[y][i];
cx1=i;
}
for (i=1;i<=n;i=i+1)
if ((i!=cy) && (c[i]-2*a[y][i]-a[x][i]>my1))
{
my1=c[i]-2*a[y][i]-a[x][i];
cy1=i;
}
if (mx1+my>my1+mx) return (mx1+my+r[x]+r[y]);
return (my1+mx+r[x]+r[y]);
}
void process(void)
{
b=-32000;
int i,j,k;
for (i=1;i<n;i=i+1)
for (j=i+1;j<=n;j=j+1)
{
k=max(i,j);
if (k>b) b=k;
}
for (i=1;i<=n;i=i+1)
for (j=1;j<n;j=j+1)
for (k=j+1;k<=n;k=k+1)
{
if (r[i]+c[j]+c[k]-2*a[i][j]-2*a[i][k]>b) b=r[i]+c[j]+c[k]-2*a[i][j]-2*a[i][k];
if (c[i]+r[j]+r[k]-2*a[j][i]-2*a[k][i]>b) b=c[i]+r[j]+r[k]-2*a[j][i]-2*a[k][i];
}
printf("%d",b);
}
int main(void)
{
init();
process();
}