#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
// what is the idea of my solution ?
/*
- get for each pair(i, j) j >= i how much I can extend it to both, top, and bottom
- then I will make sure that when I will query for something max(i, j) it will return the max in any of its subarrays
- my current solution idea should be O(n ^ 3 * (log(n ^ 3))), or something like this
*/
void chmax(int &a, int b)
{
if (a < b)
a = b;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
int n = N;
auto f = F;
vec<vec<int>> pref(n + 1, vec<int>(n + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + f[i - 1][j - 1];
auto query = [&](int i1, int j1, int i2, int j2) -> int
{
i1++, j1++, i2++, j2++;
return pref[i2][j2] - pref[i1 - 1][j2] - pref[i2][j1 - 1] + pref[i1 - 1][j1 - 1];
};
if (query(0, 0, n - 1, n - 1) <= 1)
{
if (query(0, 0, n - 1, n - 1) == 0)
{
return n * n;
}
pair<int, int> idx;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (f[i][j] == 1)
{
idx = {i + 1, j + 1};
}
}
}
int res1 = n * n - idx.first * idx.second;
int res2 = n * n - (n - idx.first + 1) * (n - idx.second + 1);
int res3 = n * n - (n - idx.first + 1) * idx.second;
int res4 = n * n - idx.first * (n - idx.second + 1);
return max({res1, res2, res3, res4});
}
if (n > 30)
{
return n * n - query(0, 0, n - 1, n - 1);
}
vec top(n, vec(n, vec<int>(n, 0))), down(top), right(top), left(top);
for (int i = 0; i < n; i++)
{
priority_queue<tuple<int, int, int>> pq;
for (int j = 0; j < n; j++)
{
if (f[i][j])
continue;
for (int k = j; k < n; k++)
{
if (f[i][k])
break;
int l = 0, r = i, ans = i;
while (l <= r)
{
int md = (l + r) / 2;
if (query(md, j, i, k) == 0)
{
r = md - 1;
ans = md;
}
else
{
l = md + 1;
}
}
pq.push({(i - ans + 1) * (k - j + 1), j, k});
}
}
while (not pq.empty())
{
auto [v, j, k] = pq.top();
pq.pop();
for (int x = j; x >= 0; x--)
for (int y = k; y < n; y++)
chmax(top[i][x][y], v);
}
for (int j = 0; j < n; j++)
{
if (f[i][j])
continue;
for (int k = j; k < n; k++)
{
if (f[i][k])
break;
int l = i, r = n - 1, ans = i;
while (l <= r)
{
int md = (l + r) / 2;
if (query(i, j, md, k) == 0)
{
l = md + 1;
ans = md;
}
else
{
r = md - 1;
}
}
pq.push({(ans - i + 1) * (k - j + 1), j, k});
}
}
while (not pq.empty())
{
auto [v, j, k] = pq.top();
pq.pop();
for (int x = j; x >= 0; x--)
for (int y = k; y < n; y++)
chmax(down[i][x][y], v);
}
for (int j = 0; j < n; j++)
{
if (f[j][i])
continue;
for (int k = j; k < n; k++)
{
if (f[k][i])
break;
int l = i, r = n - 1, ans = i;
while (l <= r)
{
int md = (l + r) / 2;
if (query(j, i, k, md) == 0)
{
l = md + 1;
ans = md;
}
else
{
r = md - 1;
}
}
pq.push({(ans - i + 1) * (k - j + 1), j, k});
}
}
while (not pq.empty())
{
auto [v, j, k] = pq.top();
pq.pop();
for (int x = j; x >= 0; x--)
for (int y = k; y < n; y++)
chmax(right[i][x][y], v);
}
for (int j = 0; j < n; j++)
{
if (f[j][i])
continue;
for (int k = j; k < n; k++)
{
if (f[k][i])
break;
int l = 0, r = i, ans = i;
while (l <= r)
{
int md = (l + r) / 2;
if (query(j, md, k, i) == 0)
{
l = md + 1;
ans = md;
}
else
{
r = md - 1;
}
}
pq.push({(i - ans + 1) * (k - j + 1), j, k});
}
}
while (not pq.empty())
{
auto [v, j, k] = pq.top();
pq.pop();
for (int x = j; x >= 0; x--)
for (int y = k; y < n; y++)
chmax(left[i][x][y], v);
}
}
int mx = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (f[i][j])
continue;
for (int k = j; k < n; k++)
{
if (f[i][k])
break;
int l = i, r = n - 1, ans = i;
while (l <= r)
{
int md = (l + r) / 2;
if (query(i, j, md, k) == 0)
{
l = md + 1;
ans = md;
}
else
r = md - 1;
}
int v = (k - j + 1) * (ans - i + 1);
if (i != 0)
{
v += top[i - 1][j][k];
// cout << top[i - 1][j][k] << ' ';
}
if (ans != n - 1)
{
v += down[ans + 1][j][k];
// cout << down[ans + 1][j][k] << ' ';
}
if (j != 0)
{
v += left[j - 1][i][ans];
// cout << left[j - 1][i][ans] << ' ';
}
if (k != n - 1)
{
v += right[k + 1][i][ans];
// cout << right[k + 1][i][ans] << ' ';
}
chmax(mx, v);
// cout << i << ' ' << ans << ' ' << j << ' ' << k << ' ' << v << '\n';
}
}
}
return mx;
}
