#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 2005;
static int n;
static vector<vector<int>> F;
static int pref[MAXN][MAXN];
// prefix sum query: number of trees in rectangle [r1..r2] x [c1..c2]
static inline int getsum(int r1, int r2, int c1, int c2) {
if (r1 > r2 || c1 > c2) return 0;
return pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
}
// list maximal empty intervals in row r within [L..R]
static vector<pair<int,int>> get_intervals(int r, int L, int R) {
vector<pair<int,int>> res;
int c = L;
while (c <= R) {
while (c <= R && F[r][c] == 1) c++;
if (c > R) break;
int s = c;
while (c <= R && F[r][c] == 0) c++;
res.push_back({s, c - 1});
}
return res;
}
// expand vertically for fixed column interval [L..R] around row r
static array<int,2> expand_vertical(int r, int L, int R) {
// find top
int lo = 0, hi = r;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (getsum(mid, r, L, R) == 0) hi = mid;
else lo = mid + 1;
}
int top = lo;
// find bottom
lo = r, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (getsum(r, mid, L, R) == 0) lo = mid;
else hi = mid - 1;
}
int bot = lo;
return {top, bot};
}
// pack (top,bot,L,R) into 64-bit key (N<=2000 fits 11 bits each)
static inline uint64_t pack_key(int top, int bot, int L, int R) {
return (uint64_t)top
| ((uint64_t)bot << 11)
| ((uint64_t)L << 22)
| ((uint64_t)R << 33);
}
static unordered_map<uint64_t, int> memo;
static int dp(int top, int bot, int L, int R) {
uint64_t key = pack_key(top, bot, L, R);
auto it = memo.find(key);
if (it != memo.end()) return it->second;
int curH = bot - top + 1;
int best = 0;
// try expand from row top-1
if (top > 0) {
for (auto [l2, r2] : get_intervals(top - 1, L, R)) {
auto tb = expand_vertical(top - 1, l2, r2);
int ntop = tb[0], nbot = tb[1];
int newH = nbot - ntop + 1;
int added = (newH - curH) * (r2 - l2 + 1);
best = max(best, dp(ntop, nbot, l2, r2) + added);
}
}
// try expand from row bot+1
if (bot + 1 < n) {
for (auto [l2, r2] : get_intervals(bot + 1, L, R)) {
auto tb = expand_vertical(bot + 1, l2, r2);
int ntop = tb[0], nbot = tb[1];
int newH = nbot - ntop + 1;
int added = (newH - curH) * (r2 - l2 + 1);
best = max(best, dp(ntop, nbot, l2, r2) + added);
}
}
memo[key] = best;
return best;
}
int biggest_stadium(int N, std::vector<std::vector<int>> forest) {
n = N;
F = std::move(forest);
// build prefix sums
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
pref[i][j] = 0;
for (int i = 0; i < n; i++) {
int rowSum = 0;
for (int j = 0; j < n; j++) {
rowSum += F[i][j];
pref[i + 1][j + 1] = pref[i][j + 1] + rowSum;
}
}
memo.clear();
memo.reserve(1 << 20);
int ans = 0;
// enumerate all core rectangles by picking an empty interval in some row
for (int r = 0; r < n; r++) {
for (auto [L, R] : get_intervals(r, 0, n - 1)) {
auto tb = expand_vertical(r, L, R);
int top = tb[0], bot = tb[1];
int area = (bot - top + 1) * (R - L + 1);
ans = max(ans, area + dp(top, bot, L, R));
}
}
return ans;
}
