#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 2e3+10;
struct Sparse {
vector<vector<int>> sparse;
Sparse() {}
Sparse(vector<int>& v) {
int n = v.size();
sparse.push_back(v);
for (int i = 1; (1 << i) <= n; i++) {
sparse.push_back(vector<int>(n - (1 << i) + 1));
for (int j = 0; j + (1 << i) <= n; j++) {
sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]);
}
}
}
int qry(int l, int r) {
assert(l <= r);
int b = 31 - __builtin_clz(r - l + 1);
// cerr << "> " << l << ' ' << r << ''
return min(sparse[b][l], sparse[b][r - (1 << b) + 1]);
}
} ones[M], twos[M];
int get_cost(int i, int l, int r) {
return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}
#include<bits/extc++.h>
struct splitmix64_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;
vector<int> impl[M][M];
vector<int> impr[M][M];
vector<int> has[M][M];
hash_map<ll, int> dp;
ll h(int a, int b, int c) {
return (long long) a * M * M + b * M + c;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
for (int i = 0; i < N; i++) {
vector<int> up(N), down(N);
for (int j = 0; j < N; j++) {
while (i - up[j] >= 0 && !F[i - up[j]][j]) up[j]++;
while (i + down[j] < N && !F[i + down[j]][j]) down[j]++;
}
ones[i] = Sparse(up), twos[i] = Sparse(down);
}
auto add_imp = [&](int i, int l, int r) {
has[l][r].push_back(i);
impl[i][l].push_back(r);
impr[i][r].push_back(l);
};
for (int i = 0; i < N; i++) {
vector<int> blocks{-1};
for (int j = 0; j < N; j++) if (F[i][j])
blocks.push_back(j);
blocks.push_back(N);
for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) {
int l = blocks[j-1]+1, r = blocks[j]-1;
for (int k = l; k <= r; k++) {
add_imp(i, k, r);
if (k != r) add_imp(i, l, k);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sort(impl[i][j].begin(), impl[i][j].end());
sort(impr[i][j].begin(), impr[i][j].end());
}
}
auto upd = [&](int ni, int l, int r, int x, int cur_cost) {
if (ni < 0 || ni >= N) return;
int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), l) - impr[ni][r].begin();
if (nl < sz(impr[ni][r])) {
nl = impr[ni][r][nl];
dp[h(ni, nl, r)] = max(dp[h(ni, nl, r)], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1));
}
int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), r) - impl[ni][l].begin() - 1;
if (nr >= 0) {
nr = impl[ni][l][nr];
dp[h(ni, l, nr)] = max(dp[h(ni, l, nr)], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
}
};
// cerr << (double) clock() / CLOCKS_PER_SEC << endl;
for (int l = 0; l < N; l++) {
for (int r = N-1; r >= 0; r--) {
for (int i : has[l][r]) {
int cur_cost = get_cost(i, l, r);
dp[h(i, l, r)] = max(dp[h(i, l, r)], cur_cost * (r - l + 1));
// cerr << l << ' ' << r << ' ' << i << ' ' << dp[{i, l, r}] << endl;
int top = i - ones[i].qry(l, r);
int bot = i + twos[i].qry(l, r);
upd(i, l, r, dp[h(i, l, r)], cur_cost);
upd(top, l, r, dp[h(i, l, r)], cur_cost);
upd(bot, l, r, dp[h(i, l, r)], cur_cost);
}
}
}
int ans = 0;
for (auto& [_, v] : dp) ans = max(ans, v);
cerr << (double) clock() / CLOCKS_PER_SEC << endl;
return ans;
}
