#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int n;
vector<vector<int>>a;
namespace sub1{
bool check_subtask(){
for(int i = 0, cnt = 0; i < n; i++){
if((cnt += accumulate(a[i].begin(), a[i].end(), 0)) > 1){
return false;
}
}
return true;
}
int solve(){
int x = -1, y;
for(int i = 0; i < n && x == -1; i++){
for(int j = 0; j < n; j++){
if(a[i][j] == 1){
x = i;
y = j;
break;
}
}
}
return n * n - (x == -1 ? 0 : min(x + 1, n - x) * min(y + 1, n - y));
}
}
namespace sub2{
bool check(int mask){
vector<vector<bool>>in(n, vector<bool>(n, false));
for(int i = 0, id = 0; i < n; i++){
for(int j = 0; j < n; j++, id++){
if(mask >> id & 1){
if(a[i][j]){
return false;
}
in[i][j] = true;
}
}
}
for(int x = 0; x < n; x++){
for(int y = 0; y < n; y++){
if(in[x][y]){
for(int u = x; u < n; u++){
for(int v = 0; v < n; v++){
if(in[u][v]){
bool flag = true;
for(int i = x; i <= u; i++){
if(!in[i][y]){
flag = false;
break;
}
}
if(flag){
for(int i = min(y, v); i <= max(y, v); i++){
if(!in[u][i]){
flag = false;
break;
}
}
}
if(!flag){
flag = true;
for(int i = u; i >= x; i--){
if(!in[i][v]){
flag = false;
break;
}
}
if(flag){
for(int i = min(y, v); i <= max(y, v); i++){
if(!in[x][i]){
flag = false;
break;
}
}
}
}
if(!flag){
return false;
}
}
}
}
}
}
}
return true;
}
int solve(){
int ans = 0;
for(int mask = (1 << (n * n)) - 1; mask > 0; mask--){
int popcount = __builtin_popcount(mask);
if(popcount > ans && check(mask)){
ans = popcount;
}
}
return ans;
}
}
const int INF = 1e9;
namespace sub3{
vector<pair<int, int>>range[7];
int f[7][7][7][7][7][7];
bool cover(pair<int, int>a, pair<int, int>b){
return a.first <= b.first && a.second >= b.second;
}
bool satisfy(pair<int, int>a, pair<int, int>b){
return cover(a, b) || cover(b, a);
}
int dp(int i, int j, pair<int, int>ir, pair<int, int>jr){
if(i > j){
return 0;
}
int& ans = f[i][j][ir.first][ir.second][jr.first][jr.second];
if(ans != -1){
return ans;
}
ans = -INF;
if(i == j){
for(pair<int, int>& r : range[i]){
if((cover(r, ir) && cover(r, jr)) || (cover(r, ir) && cover(jr, r)) || (cover(r, jr) && cover(ir, r))){
maximize(ans, r.second - r.first + 1);
}
}
}
else if(ir.first <= jr.first && ir.second >= jr.second){
for(pair<int, int>& it : range[j]){
if(it.first <= jr.first && it.second >= jr.second && satisfy(it, ir)){
maximize(ans, dp(i, j - 1, ir, it) + it.second - it.first + 1);
}
}
}
else{
for(pair<int, int>& it : range[i]){
if(it.first <= ir.first && it.second >= ir.second && satisfy(it, jr)){
maximize(ans, dp(i + 1, j, it, jr) + it.second - it.first + 1);
}
}
}
return ans;
}
int solve(){
int ans = 0;
for(int i = 0; i < n; i++){
for(int l = 0; l < n; l++){
for(int r = l; r < n; r++){
if(a[i][r]){
break;
}
range[i].push_back(make_pair(l, r));
maximize(ans, r - l + 1);
}
}
}
memset(f, -1, sizeof(f));
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
for(pair<int, int>& iti : range[i]){
for(pair<int, int>& itj : range[j]){
if(satisfy(iti, itj)){
maximize(ans, iti.second - iti.first + itj.second - itj.first + 2 + dp(i + 1, j - 1, iti, itj));
}
}
}
}
}
return ans;
}
}
namespace sub4{
int f[30][30][30][30];
vector<pair<int, int>>range[30];
bool cover(pair<int, int>a, pair<int, int>b){
return a.first <= b.first && a.second >= b.second;
}
int dp(int i, int j, pair<int, int>r){
if(i == 0 && j == n){
return 0;
}
int& ans = f[i][j][r.first][r.second];
if(ans != -1){
return ans;
}
if(i > (ans = 0)){
for(pair<int, int>& it : range[i - 1]){
if(cover(r, it)){
maximize(ans, dp(i - 1, j, it) + it.second - it.first + 1);
}
}
}
if(j + 1 < n){
for(pair<int, int>& it : range[j + 1]){
if(cover(r, it)){
maximize(ans, dp(i, j + 1, it) + it.second - it.first + 1);
}
}
}
return ans;
}
int solve(){
int ans = 0;
for(int i = 0; i < n; i++){
for(int l = 0; l < n; l++){
for(int r = l; r < n; r++){
if(a[i][r]){
break;
}
range[i].push_back(make_pair(l, r));
}
}
}
memset(f, -1, sizeof(f));
for(int i = 0; i < n; i++){
for(pair<int, int>& it : range[i]){
maximize(ans, dp(i, i, it) + it.second - it.first + 1);
}
}
return ans;
}
}
namespace sub56{
const int lim = 2e3 + 5;
int left[lim][lim], right[lim][lim], up[lim][lim], f[lim][lim];
vector<pair<int, int>>vert[lim];
int solve(){
a.insert(a.begin(), vector<int>());
for(int i = 1; i <= n; i++){
a[i].insert(a[i].begin(), -1);
}
memset(up[0], 0, sizeof(up[0]));
for(int i = 1; i <= n; i++){
left[i][0] = 0;
for(int j = 1; j <= n; j++){
left[i][j] = a[i][j] ? j : left[i][j - 1];
up[i][j] = a[i][j] ? i : up[i - 1][j];
if(!a[i][j]){
vert[i - up[i][j]].push_back(make_pair(i, j));
}
}
right[i][n + 1] = n + 1;
for(int j = n; j > 0; j--){
right[i][j] = a[i][j] ? j : right[i][j + 1];
}
}
int ans = 0;
for(int len = 1; len <= n; len++){
for(auto& [i, j] : vert[len]){
if(len > 1){
maximize(left[i][j], left[i - 1][j]);
minimize(right[i][j], right[i - 1][j]);
}
int l = left[i][j], r = right[i][j];
maximize(ans, f[i][j] = max({f[i - 1][j] + r - l - 1, f[i][l] + (up[i][l] - up[i][j]) * (r - l - 1), f[i][r] + (up[i][r] - up[i][j]) * (r - l - 1)}));
}
}
return ans;
}
}
int biggest_stadium(int _n, vector<vector<int>>_a){
n = _n;
swap(a, _a);
if(sub1::check_subtask()){
return sub1::solve();
}
if(n <= 3){
return sub2::solve();
}
if(n <= 7){
return sub3::solve();
}
if(n <= 30){
return sub4::solve();
}
return sub56::solve();
}
