#define _CRT_SECURE_NO_WARNINGS
#include "soccer.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <bitset>
#include <cassert>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen(".out", "w", stdout);
ll gcd(ll a, ll b)
{
if (a == 0 || b == 0) {
return max(a, b);
}
if (a <= b) {
return gcd(a, b % a);
}
else {
return gcd(a % b, b);
}
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
const int N = 2005;
const ll oo = 1000000000000000000, MOD = 1000000007;
int n = N, qan = 0;
int F[N][N];
bool ok[N][N];
vector<pair<int,int>> ara(pair<int, int> mm) {
int r = mm.fr, c = mm.sc;
vector<pair<int, int>> hasnuma1;
for (int k = c; k >= 0; --k) {
if (F[r][k] == 1) {
break;
}
ok[r][k] = 1;
hasnuma1.pb({ r,k });
}
for (int k = c + 1; k < n; ++k) {
if (F[r][k] == 1) {
break;
}
ok[r][k] = 1;
hasnuma1.pb({ r,k });
}
for (int k = r; k >= 0; --k) {
if (F[k][c] == 1) {
break;
}
ok[k][c] = 1;
hasnuma1.pb({ k,c });
}
for (int k = r + 1; k < n; ++k) {
if (F[k][c] == 1) {
break;
}
ok[k][c] = 1;
hasnuma1.pb({ k,c });
}
return hasnuma1;
}
int biggest_stadium(int N, std::vector<std::vector<int>> f) {
n = N;
pair<int, int> stex = { -1,-1 };
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j){
F[i][j] = f[i][j];
if (F[i][j] == 1) {
stex = { i,j };
++qan;
}
}
}
if (stex.fr == -1) {
return (n * n);
}
if (qan == n * n) {
return 0;
}
if (n == 2) {
if (F[0][0] == 1 && F[1][1] == 1) {
return 1;
}
return (n * n - qan);
}
int ans = 0;
for (int i = 0; i < (1 << 9); ++i) {
vector<int> vec;
for (int j = 0; j < 9; ++j) {
if (((1 << j) & i) != 0) {
vec.pb(j);
}
}
bool fl = 0;
for (int j = 0; j < vec.size(); ++j) {
int r = vec[i] / 3;
int c = vec[i] - r * 3;
if (F[r][c] == 1) {
fl = 1;
break;
}
}
if (fl) {
continue;
}
bool fl1 = 1;
for (int j = 0; j < vec.size(); ++j) {
int r = vec[i] / 3;
int c = vec[i] - r * 3;
for (int k = 0; k < n; ++k) {
for (int l = 0; l < n; ++l) {
ok[k][l] = 0;
}
}
vector<pair<int, int>> hasnuma1 = ara({ r, c });
for (int k = 0; k < hasnuma1.size(); ++k) {
vector<pair<int,int>> vec2;
vec2 = ara(hasnuma1[k]);
}
for (int k = 0; k < vec.size(); ++k) {
int r1 = vec[k] / 3;
int c1 = vec[k] - r * 3;
if (ok[r1][c1] != 1) {
fl1 = 0;
break;
}
}
}
if (fl1) {
ans = max(ans, (int)vec.size());
}
}
return ans;
/*int jj = stex.sc;
int ii = stex.fr;
int ver = stex.fr - 1;
int ner = n - stex.fr;
int dzax = stex.sc - 1;
int aj = n - stex.sc;
int ans = ner * (n - aj) + n * (aj);
ans = max(ans, n * dzax + ner * (n - dzax));
ans = max(ans, n * dzax + ver * (n - dzax));
ans = max(ans, n * aj + ver * (n - aj));
return ans;*/
}
