#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 2003;
const int MAXM = 501;
const int lx[] = {-1, 0, 0, 1}, ly[] = {0, -1, 1, 0};
struct State {
int x, y, t;
State(int _x = 0, int _y = 0, int _t = 0) : x(_x), y(_y), t(_t) {};
};
ii range[MAXN], max_rec[MAXM][MAXM][MAXM];
int dp[2][MAXM][MAXM][MAXM];
int sum[MAXN][MAXN], nSize;
bool dx[MAXN][MAXN][4], tmp[MAXN][MAXN], isTree[MAXN][MAXN];
bool checkGrid2(void) {
int minL(nSize), maxR(0);
bool ok(0);
for (int i = 1; i <= nSize; ++i) {
range[i] = {0, 0};
bool hasEmpty(0);
for (int j = 1; j <= nSize; ++j) {
if(hasEmpty && isTree[i][j - 1] && !isTree[i][j])
return false;
hasEmpty |= (!isTree[i][j]);
if(!isTree[i][j]) {
range[i].se = j;
if(!range[i].fi)
range[i].fi = j;
}
}
if(ok && range[i].fi > 0 && range[i - 1].fi == 0)
return false;
ok |= (range[i].fi > 0);
if(range[i].fi > 0)
minL = min(minL, range[i].fi);
maxR = max(maxR, range[i].se);
}
int upL(-1), upR(-1), downL(-1), downR(-1);
int leftL(-1), leftR(-1), rightL(-1), rightR(-1);
bool descL(0), descR(0);
for (int i = 1; i <= nSize; ++i) {
if(range[i].fi == 0)
continue;
if(i > 2 && descL && range[i - 1].fi > range[i].fi)
return false;
if(i > 2 && descR && range[i - 1].se < range[i].se)
return false;
if(i > 1 && range[i - 1].fi > 0 && range[i - 1].fi < range[i].fi)
descL = 1;
if(i > 1 && range[i - 1].se > 0 && range[i - 1].se > range[i].se)
descR = 1;
if(upL < 0)
upL = range[i].fi, upR = range[i].se;
downL = range[i].fi, downR = range[i].se;
if(range[i].fi == minL) {
leftR = i;
if(leftL < 0)
leftL = i;
}
if(range[i].se == maxR) {
rightR = i;
if(rightL < 0)
rightL = i;
}
}
for (int i = 1; i <= nSize; ++i) {
if(range[i].fi <= 0)
continue;
int nowL = range[i].fi, nowR = range[i].se;
if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
return false;
}
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
if(!isTree[j][i]) {
int k(j);
while(k <= nSize && !isTree[k][i])
++k;
--k;
if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
return false;
break;
}
}
}
return true;
}
int calc(int i, int j) {
return (i - 1 + j - 1) * nSize - (i - 1) * (j - 1);
}
int sub1(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
if(isTree[i][j]) {
return max({calc(i, j), calc(nSize - i + 1, j), calc(i, nSize - j + 1), calc(nSize - i + 1, nSize - j + 1)});
}
}
}
abort();
}
int sub2(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
tmp[i][j] = isTree[i][j];
}
int res(0);
for (int mask = 0; mask < (1 << (nSize * nSize)); ++mask) {
if(__builtin_popcount(mask) <= res)
continue;
bool check(1);
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
if((mask >> ((i - 1) * nSize + j - 1) & 1) && isTree[i][j])
check = 0;
isTree[i][j] = !(mask >> ((i - 1) * nSize + j - 1) & 1);
}
}
if(check && checkGrid2())
res = __builtin_popcount(mask);
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
isTree[i][j] = tmp[i][j];
}
}
return res;
}
inline int getSum(int x, int y, int u, int v) {
return sum[u][v] - sum[u][y - 1] - sum[x - 1][v] + sum[x - 1][y - 1];
}
int sub4(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + isTree[i][j];
}
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
for (int i = 1; i <= nSize; ++i) {
dp[0][i][l][r] = dp[1][i][l][r] = 0;
}
}
}
for (int i = 1; i <= nSize; ++i) {
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
if(isTree[i][r])
break;
dp[1][i][l][r] = r - l + 1;
}
}
}
int res(0);
for (int len = 1; len <= nSize; ++len) {
int pre(len & 1), cur(!pre);
for (int i = 1; i + len - 1 <= nSize; ++i) {
int j(i + len - 1);
for (int l = 1; l <= nSize; ++l) {
for (int r = nSize; r >= l; --r) {
if(!dp[pre][i][l][r])
continue;
if(i > 1 && getSum(i - 1, l, i - 1, r) == 0)
dp[cur][i - 1][l][r] = max(dp[cur][i - 1][l][r], dp[pre][i][l][r] + r - l + 1);
if(j < nSize && getSum(j + 1, l, j + 1, r) == 0)
dp[cur][i][l][r] = max(dp[cur][i][l][r], dp[pre][i][l][r] + r - l + 1);
if(l < r) {
dp[pre][i][l + 1][r] = max(dp[pre][i][l + 1][r], dp[pre][i][l][r]);
dp[pre][i][l][r - 1] = max(dp[pre][i][l][r - 1], dp[pre][i][l][r]);
}
res = max(res, dp[pre][i][l][r]);
dp[pre][i][l][r] = 0;
}
}
}
}
return res;
}
int sub5(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + isTree[i][j];
}
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
int j(1);
for (int i = 1; i <= nSize; ++i) {
j = max(j, i);
while(j < nSize && getSum(i, l, j + 1, r) == 0)
++j;
max_rec[i][l][r].se = j;
}
j = nSize;
for (int i = nSize; i > 0; --i) {
j = min(j, i);
while(j > 1 && getSum(j - 1, l, i, r) == 0)
--j;
max_rec[i][l][r].fi = j;
}
}
}
for (int i = 1; i <= nSize; ++i) {
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
if(max_rec[i][l][r].fi == i && getSum(i, l, i, r) == 0) {
dp[0][i][l][r] = (max_rec[i][l][r].se - max_rec[i][l][r].fi + 1) * (r - l + 1);
} else {
dp[0][i][l][r] = 0;
}
}
}
}
int res(0);
for (int i = nSize; i > 0; --i) {
for (int l = 1; l <= nSize; ++l) {
for (int r = nSize; r >= l; --r) {
if(!dp[0][i][l][r])
continue;
ii rec = max_rec[i][l][r];
if(l < r) {
ii new_rec = max_rec[i][l + 1][r];
dp[0][i][l + 1][r] = max(dp[0][i][l + 1][r], dp[0][i][l][r] + (new_rec.se - new_rec.fi + 1 - (rec.se - rec.fi + 1)) * (r - l));
new_rec = max_rec[i][l][r - 1];
dp[0][i][l][r - 1] = max(dp[0][i][l][r - 1], dp[0][i][l][r] + (new_rec.se - new_rec.fi + 1 - (rec.se - rec.fi + 1)) * (r - l));
}
res = max(res, dp[0][i][l][r]);
dp[0][i][l][r] = 0;
}
}
}
return res;
}
int biggest_stadium(int n, vector<vector<int>> F) {
nSize = n;
int cntTree(0);
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
isTree[i][j] = (F[i - 1][j - 1]);
cntTree += isTree[i][j];
}
}
if(cntTree == 1)
return sub1();
if(nSize <= 3)
return sub2();
if(cntTree == 0 || checkGrid2())
return nSize * nSize - cntTree;
if(nSize <= 30)
return sub4();
if(nSize <= 500)
return sub5();
return 1;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "soccer"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<vector<int>> F;
int n;
cin >> n;
F.resize(n);
for (int i = 0; i < n; ++i) {
F[i].resize(n);
for (int j = 0; j < n; ++j) {
cin >> F[i][j];
//F[i][j] = min(1, max(0, Random(-4, 1))); cout << F[i][j] << " \n"[j + 1 == n];
}
}
int ans = biggest_stadium(n, F);
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
