#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 2003;
const int MAXM = 501;
const int lx[] = {-1, 0, 0, 1}, ly[] = {0, -1, 1, 0};
struct State {
int x, y, t;
State(int _x = 0, int _y = 0, int _t = 0) : x(_x), y(_y), t(_t) {};
};
ii range[MAXN], max_rec[MAXM][MAXM][MAXM];
int f[MAXN * MAXN], nxt[2][MAXN][MAXN], dp[2][MAXM][MAXM][MAXM];
int sum[MAXN][MAXN], up[MAXN][MAXN], down[MAXN][MAXN], nSize;
bool dx[MAXN][MAXN][4], tmp[MAXN][MAXN], isTree[MAXN][MAXN];
bool checkGrid2(void) {
int minL(nSize), maxR(0);
bool ok(0);
for (int i = 1; i <= nSize; ++i) {
range[i] = {0, 0};
bool hasEmpty(0);
for (int j = 1; j <= nSize; ++j) {
if(hasEmpty && isTree[i][j - 1] && !isTree[i][j])
return false;
hasEmpty |= (!isTree[i][j]);
if(!isTree[i][j]) {
range[i].se = j;
if(!range[i].fi)
range[i].fi = j;
}
}
if(ok && range[i].fi > 0 && range[i - 1].fi == 0)
return false;
ok |= (range[i].fi > 0);
if(range[i].fi > 0)
minL = min(minL, range[i].fi);
maxR = max(maxR, range[i].se);
}
int upL(-1), upR(-1), downL(-1), downR(-1);
int leftL(-1), leftR(-1), rightL(-1), rightR(-1);
bool descL(0), descR(0);
for (int i = 1; i <= nSize; ++i) {
if(range[i].fi == 0)
continue;
if(i > 2 && descL && range[i - 1].fi > range[i].fi)
return false;
if(i > 2 && descR && range[i - 1].se < range[i].se)
return false;
if(i > 1 && range[i - 1].fi > 0 && range[i - 1].fi < range[i].fi)
descL = 1;
if(i > 1 && range[i - 1].se > 0 && range[i - 1].se > range[i].se)
descR = 1;
if(upL < 0)
upL = range[i].fi, upR = range[i].se;
downL = range[i].fi, downR = range[i].se;
if(range[i].fi == minL) {
leftR = i;
if(leftL < 0)
leftL = i;
}
if(range[i].se == maxR) {
rightR = i;
if(rightL < 0)
rightL = i;
}
}
for (int i = 1; i <= nSize; ++i) {
if(range[i].fi <= 0)
continue;
int nowL = range[i].fi, nowR = range[i].se;
if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
return false;
}
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
if(!isTree[j][i]) {
int k(j);
while(k <= nSize && !isTree[k][i])
++k;
--k;
if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
return false;
break;
}
}
}
return true;
}
int calc(int i, int j) {
return (i - 1 + j - 1) * nSize - (i - 1) * (j - 1);
}
int sub1(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
if(isTree[i][j]) {
return max({calc(i, j), calc(nSize - i + 1, j), calc(i, nSize - j + 1), calc(nSize - i + 1, nSize - j + 1)});
}
}
}
abort();
}
int sub2(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
tmp[i][j] = isTree[i][j];
}
int res(0);
for (int mask = 0; mask < (1 << (nSize * nSize)); ++mask) {
if(__builtin_popcount(mask) <= res)
continue;
bool check(1);
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
if((mask >> ((i - 1) * nSize + j - 1) & 1) && isTree[i][j])
check = 0;
isTree[i][j] = !(mask >> ((i - 1) * nSize + j - 1) & 1);
}
}
if(check && checkGrid2())
res = __builtin_popcount(mask);
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
isTree[i][j] = tmp[i][j];
}
}
return res;
}
inline int getSum(int x, int y, int u, int v) {
return sum[u][v] - sum[u][y - 1] - sum[x - 1][v] + sum[x - 1][y - 1];
}
int sub4(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + isTree[i][j];
}
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
for (int i = 1; i <= nSize; ++i) {
dp[0][i][l][r] = dp[1][i][l][r] = 0;
}
}
}
for (int i = 1; i <= nSize; ++i) {
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
if(isTree[i][r])
break;
dp[1][i][l][r] = r - l + 1;
}
}
}
int res(0);
for (int len = 1; len <= nSize; ++len) {
int pre(len & 1), cur(!pre);
for (int i = 1; i + len - 1 <= nSize; ++i) {
int j(i + len - 1);
for (int l = 1; l <= nSize; ++l) {
for (int r = nSize; r >= l; --r) {
if(!dp[pre][i][l][r])
continue;
if(i > 1 && getSum(i - 1, l, i - 1, r) == 0)
dp[cur][i - 1][l][r] = max(dp[cur][i - 1][l][r], dp[pre][i][l][r] + r - l + 1);
if(j < nSize && getSum(j + 1, l, j + 1, r) == 0)
dp[cur][i][l][r] = max(dp[cur][i][l][r], dp[pre][i][l][r] + r - l + 1);
if(l < r) {
dp[pre][i][l + 1][r] = max(dp[pre][i][l + 1][r], dp[pre][i][l][r]);
dp[pre][i][l][r - 1] = max(dp[pre][i][l][r - 1], dp[pre][i][l][r]);
}
res = max(res, dp[pre][i][l][r]);
dp[pre][i][l][r] = 0;
}
}
}
}
return res;
}
int sub5(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + isTree[i][j];
}
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
int j(1);
for (int i = 1; i <= nSize; ++i) {
j = max(j, i);
while(j < nSize && getSum(i, l, j + 1, r) == 0)
++j;
max_rec[i][l][r].se = j;
}
j = nSize;
for (int i = nSize; i > 0; --i) {
j = min(j, i);
while(j > 1 && getSum(j - 1, l, i, r) == 0)
--j;
max_rec[i][l][r].fi = j;
}
}
}
for (int i = 1; i <= nSize; ++i) {
for (int l = 1; l <= nSize; ++l) {
for (int r = l; r <= nSize; ++r) {
if(max_rec[i][l][r].fi == i && getSum(i, l, i, r) == 0) {
dp[0][i][l][r] = (max_rec[i][l][r].se - max_rec[i][l][r].fi + 1) * (r - l + 1);
} else {
dp[0][i][l][r] = 0;
}
}
}
}
int res(0);
for (int i = nSize; i > 0; --i) {
for (int l = 1; l <= nSize; ++l) {
for (int r = nSize; r >= l; --r) {
if(!dp[0][i][l][r])
continue;
int recSize = max_rec[i][l][r].se - max_rec[i][l][r].fi;
if(l < r) {
ii new_rec = max_rec[i][l + 1][r];
dp[0][i][l + 1][r] = max(dp[0][i][l + 1][r], dp[0][i][l][r] + (new_rec.se - new_rec.fi - recSize) * (r - l));
new_rec = max_rec[i][l][r - 1];
dp[0][i][l][r - 1] = max(dp[0][i][l][r - 1], dp[0][i][l][r] + (new_rec.se - new_rec.fi - recSize) * (r - l));
}
res = max(res, dp[0][i][l][r]);
dp[0][i][l][r] = 0;
}
}
}
return res;
}
template<int LOG = 12> struct SparseTable {
array<array<int, LOG>, MAXN> P;
SparseTable() {};
SparseTable(int N, int C[]) {
for (int i = 1; i <= N; ++i)
P[i][0] = C[i];
for (int j = 1; (1 << j) <= N; ++j) {
for (int i = 1; i + (1 << j) - 1 <= N; ++i)
P[i][j] = min(P[i][j - 1], P[i + (1 << (j - 1))][j - 1]);
}
}
int query(int l, int r) {
int log = 31 - __builtin_clz(r - l + 1);
return min(P[l][log], P[r - (1 << log) + 1][log]);
}
};
SparseTable<> up_rmq[MAXN], down_rmq[MAXN];
vector<array<int, 4>> rects;
map<array<int, 4>, int> idRec;
void gen_rectangle(void) {
for (int i = 1; i <= nSize; ++i) {
stack<array<int, 4>> st;
for (int j = 1; j <= nSize + 1; ++j) {
int cur_h = (j <= nSize) ? up[i][j] : 0;
int cur_start = j, cur_w = 1, cur_based = (i == nSize || isTree[i + 1][j]);
while(sz(st) && st.top()[2] >= cur_h) {
array<int, 4> p(st.top()); st.pop();
int start(p[0]), w(p[1]), h(p[2]), based(p[3]);
if(based && h > cur_h) {
rects.push_back({i - h + 1, start, i, start + w - 1});
idRec[rects.back()] = sz(rects) - 1;
}
cur_based |= based;
cur_start = start;
cur_w += w;
}
st.push({cur_start, cur_w, cur_h, cur_based});
}
}
}
void init(void) {
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
up[i][j] = (isTree[i][j]) ? 0 : 1 + up[i - 1][j];
down[nSize - i + 1][j] = (isTree[nSize - i + 1][j]) ? 0 : 1 + down[nSize - i + 2][j];
}
nxt[0][i][nSize] = nxt[1][i][nSize] = nSize + 1;
for (int j = nSize - 1; j > 0; --j) {
int c(isTree[i][j + 1]);
nxt[c][i][j] = j + 1;
nxt[1 - c][i][j] = nxt[1 - c][i][j + 1];
}
}
for (int i = 1; i <= nSize; ++i) {
up_rmq[i] = SparseTable<>(nSize, up[i]);
down_rmq[i] = SparseTable<>(nSize, down[i]);
}
gen_rectangle();
}
int solve(int id_rec) {
int &ans(f[id_rec]);
if(ans != -1)
return ans;
int a = rects[id_rec][0], b = rects[id_rec][1];
int c = rects[id_rec][2], d = rects[id_rec][3];
int area = (c - a + 1) * (d - b + 1);
ans = area;
if(a > 1) {
int start = (!isTree[a - 1][b]) ? b : nxt[0][a - 1][b];
for (int l = start; l <= d; ) {
int r = min(nSize, nxt[1][a - 1][l] - 1);
if(l == b && r == d)
break;
int u = a - up_rmq[a].query(l, r) + 1;
int d = c + down_rmq[c].query(l, r) - 1;
if(idRec.find({u, l, d, r}) != idRec.end()) {
int new_id_rec = idRec[{u, l, d, r}];
ans = max(ans, area + solve(new_id_rec) - (c - a + 1) * (r - l + 1));
}
l = nxt[0][a - 1][r];
}
}
if(c < nSize) {
int start = (!isTree[c + 1][b]) ? b : nxt[0][c + 1][b];
for (int l = start; l <= d; ) {
int r = min(nSize, nxt[1][c + 1][l] - 1);
if(l == b && r == d)
break;
int u = a - up_rmq[a].query(l, r) + 1;
int d = c + down_rmq[c].query(l, r) - 1;
if(idRec.find({u, l, d, r}) != idRec.end()) {
int new_id_rec = idRec[{u, l, d, r}];
ans = max(ans, area + solve(new_id_rec) - (c - a + 1) * (r - l + 1));
}
l = nxt[0][c + 1][r];
}
}
return ans;
}
int magicFunc(void) {
init();
for (int i = 0; i < sz(rects); ++i)
f[i] = -1;
int res(0);
for (int i = 0; i < sz(rects); ++i)
res = max(res, solve(i));
return res;
}
int biggest_stadium(int n, vector<vector<int>> F) {
nSize = n;
int cntTree(0);
for (int i = 1; i <= nSize; ++i) {
for (int j = 1; j <= nSize; ++j) {
isTree[i][j] = (F[i - 1][j - 1]);
cntTree += isTree[i][j];
}
}
if(cntTree == 1)
return sub1();
if(nSize <= 3)
return sub2();
if(cntTree == 0 || checkGrid2())
return nSize * nSize - cntTree;
if(nSize <= 30)
return sub4();
if(nSize <= 500)
return sub5();
return magicFunc();
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "soccer"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<vector<int>> F;
int n;
cin >> n;
F.resize(n);
for (int i = 0; i < n; ++i) {
F[i].resize(n);
for (int j = 0; j < n; ++j) {
cin >> F[i][j];
//F[i][j] = min(1, max(0, Random(-4, 1))); cout << F[i][j] << " \n"[j + 1 == n];
}
}
int ans = biggest_stadium(n, F);
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
Compilation message
soccer.cpp: In function 'bool checkGrid2()':
soccer.cpp:100:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
100 | if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
soccer.cpp:100:91: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
100 | if(!(nowL <= upL && upR <= nowR || upL <= nowL && nowR <= upR) || !(nowL <= downL && downR <= nowR || downL <= nowL && nowR <= downR))
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:112:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
112 | if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
| ~~~~~~~~~~~^~~~~~~~~~~~~
soccer.cpp:112:93: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
112 | if(!(j <= leftL && leftR <= k || leftL <= j && k <= leftR) || !(j <= rightL && rightR <= k || rightL <= j && k <= rightR))
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
/tmp/ccaAoBnF.o: in function `checkGrid2()':
soccer.cpp:(.text+0x25): relocation truncated to fit: R_X86_64_PC32 against symbol `range' defined in .bss section in /tmp/ccaAoBnF.o
soccer.cpp:(.text+0x10e): relocation truncated to fit: R_X86_64_PC32 against symbol `range' defined in .bss section in /tmp/ccaAoBnF.o
soccer.cpp:(.text+0x242): relocation truncated to fit: R_X86_64_PC32 against symbol `range' defined in .bss section in /tmp/ccaAoBnF.o
/tmp/ccaAoBnF.o: in function `Random(int, int)':
soccer.cpp:(.text+0x10ee): relocation truncated to fit: R_X86_64_PC32 against symbol `rng' defined in .bss section in /tmp/ccaAoBnF.o
/tmp/ccaAoBnF.o: in function `_GLOBAL__sub_I_rng':
soccer.cpp:(.text.startup+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
soccer.cpp:(.text.startup+0x25): relocation truncated to fit: R_X86_64_PC32 against `.bss'
soccer.cpp:(.text.startup+0x36): relocation truncated to fit: R_X86_64_PC32 against symbol `rng' defined in .bss section in /tmp/ccaAoBnF.o
soccer.cpp:(.text.startup+0x48): relocation truncated to fit: R_X86_64_PC32 against symbol `rng' defined in .bss section in /tmp/ccaAoBnF.o
soccer.cpp:(.text.startup+0x89): relocation truncated to fit: R_X86_64_PC32 against symbol `rng' defined in .bss section in /tmp/ccaAoBnF.o
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
