#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
void upMax(int &x, int y) {
x = max(x, y);
}
int sub1(int N, vector<vector<int>> F) {
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
if(F[i][j] == 1) {
return max({
N * i + N * j - i * j,
N * i + N * (N - j - 1) - i * (N - j - 1),
N * (N - i - 1) + N * j - (N - i - 1) * j,
N * (N - i - 1) + N * (N - j - 1) - (N - i - 1) * (N - j - 1)
});
}
}
}
return N * N;
}
int sub4(int N, vector<vector<int>> F) {
for(int i = 0; i < N; i ++) {
partial_sum(F[i].begin(), F[i].end(), F[i].begin());
}
auto get_sum = [&] (int row, int l, int r) {
return F[row][r] - (!l ? 0 : F[row][l - 1]);
};
vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>> (N, vector<vector<int>> (N, vector<int> (N, -1))));
int result = 0;
for(int first_row = N - 1; first_row >= 0; first_row --) {
for(int last_row = first_row; last_row < N; last_row ++) {
for(int l = 0; l < N; l ++) {
for(int r = l; r < N; r ++) {
if(!get_sum(first_row, l, r)) {
dp[first_row][first_row][l][r] = r - l + 1;
upMax(result, dp[first_row][first_row][l][r]);
}
}
}
for(int l = 0; l < N; l ++) {
for(int r = l; r < N; r ++) {
for(int _l = l; _l <= r; _l ++) {
for(int _r = _l; _r <= r; _r ++) {
if(first_row + 1 < N && dp[first_row + 1][last_row][l][r] != -1 && !get_sum(first_row, _l, _r)) {
upMax(dp[first_row][last_row][_l][_r], dp[first_row + 1][last_row][l][r] + _r - _l + 1);
}
if(last_row - 1 >= 0 && dp[first_row][last_row - 1][l][r] != -1 && !get_sum(last_row, _l, _r)) {
upMax(dp[first_row][last_row][_l][_r], dp[first_row][last_row - 1][l][r] + _r - _l + 1);
}
upMax(result, dp[first_row][last_row][_l][_r]);
}
}
}
}
}
}
return result;
}
int biggest_stadium(int N, vector<vector<int>> F) {
if(N <= 30) return sub4(N, F);
return sub1(N, F);
}
/*int main() {
int N;
cin >> N;
vector<vector<int>> F(N, vector<int> (N));
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
cin >> F[i][j];
}
}
cout << biggest_stadium(N, F) << "\n";
return 0;
}*/
