#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 3;
bool f[N][N];
int prefix[N][N];
int p2[N][N][N], prv[N][N][N], nxt[N][N][N];
int n;
pair<int, bool> dp[N][N][N];
int get_sum(int i, int l, int r){
if(l == 0)
return prefix[i][r];
return prefix[i][r] - prefix[i][l - 1];
}
bool bad(int l1, int r1, int l2, int r2){
if(l1 <= l2 && r2 <= r1)
return false;
if(l2 <= l1 && r1 <= r2)
return false;
return true;
}
pair<int, int> extend(int i, int j, int l, int r){
assert(prv[l][r][i] == prv[l][r][j]);
assert(nxt[l][r][i] == nxt[l][r][j]);
return {prv[l][r][i], nxt[l][r][j]};
}
int solve(int i, int j, int l, int r){
auto &[ans, solved] = dp[i][l][r];
if(solved)
return ans;
ans = 0;
solved = true;
if(l != r){
vector<pair<int, int>> v{{l + 1, r}, {l, r - 1}};
for(auto [l2, r2]: v){
auto [i2, j2] = extend(i, j, l2, r2);
int cand = (i - i2 + j2 - j) * (r2 - l2 + 1);
cand += solve(i2, j2, l2, r2);
ans = max(ans, cand);
}
}
return ans;
}
int biggest_stadium(int _N, std::vector<std::vector<int>> F){
n = _N;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
f[i][j] = F[i][j];
for(int i = 0; i < n; ++i){
prefix[i][0] = f[i][0];
for(int j = 1; j < n; ++j)
prefix[i][j] = prefix[i][j - 1] + f[i][j];
}
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int i = 0; i < n; ++i){
p2[l][r][i] = get_sum(i, l, r);
}
}
}
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
int x = 0;
for(int i = 0; i < n; ++i){
if(p2[l][r][i]){
x = i + 1;
}
else{
prv[l][r][i] = x;
}
}
x = n - 1;
for(int i = n - 1; i >= 0; --i){
if(p2[l][r][i]){
x = i - 1;
}
else{
nxt[l][r][i] = x;
}
}
}
}
int ans = 0;
for(int i = 0; i < n; ++i){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
if(f[i][r])
break;
auto [l2, r2] = extend(i, i, l, r);
ans = max(ans, solve(l2, r2, l, r) + (r - l + 1) * (r2 - l2 + 1));
}
}
}
return ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/
Compilation message
/tmp/ccSym5qN.o: in function `get_sum(int, int, int)':
soccer.cpp:(.text+0xd): relocation truncated to fit: R_X86_64_PC32 against symbol `prefix' defined in .bss section in /tmp/ccSym5qN.o
/tmp/ccSym5qN.o: in function `biggest_stadium(int, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
soccer.cpp:(.text+0x2fe): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccSym5qN.o
soccer.cpp:(.text+0x348): relocation truncated to fit: R_X86_64_PC32 against symbol `prefix' defined in .bss section in /tmp/ccSym5qN.o
soccer.cpp:(.text+0x35a): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccSym5qN.o
soccer.cpp:(.text+0x3c8): relocation truncated to fit: R_X86_64_PC32 against symbol `prefix' defined in .bss section in /tmp/ccSym5qN.o
soccer.cpp:(.text+0x573): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccSym5qN.o
/tmp/ccSym5qN.o: in function `_GLOBAL__sub_I_f':
soccer.cpp:(.text.startup+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
soccer.cpp:(.text.startup+0x29): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/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): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
