#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
using namespace std;
const int Max = 3001, Inf = 1e9, TLE = 3e6;
#define ll unsigned long long
int lg[Max], cnt;
struct SPTMIN
{
vector <vector <int>> spt;
int query(int i, int j){
int x = lg[j-i+1];
return min(spt[i][x], spt[j - (1LL << x) + 1][x]);
}
SPTMIN(vector <int> v)
{
int n = v.size();
spt.assign(n + 1, vector <int> (lg[n] + 1, Inf));
for(int j = 0; j < lg[n]+1; j++)
{
for(int i = 0; i < n; i++){
if(j == 0){
spt[i][j] = v[i];
continue;
}
spt[i][j] = spt[i][j-1];
if(i + (1LL << (j-1)) < n) spt[i][j] = min(spt[i][j-1], spt[i + (1LL << (j-1))][j-1]);
}
}
}
};
struct SPTMAX
{
vector <vector <int>> spt;
int query(int i, int j){
int x = lg[j-i+1];
return max(spt[i][x], spt[j - (1LL << x) + 1][x]);
}
SPTMAX(vector <int> v)
{
int n = v.size();
spt.assign(n + 1, vector <int> (lg[n] + 1, 0));
for(int j = 0; j < lg[n]+1; j++)
{
for(int i = 0; i < n; i++){
if(j == 0){
spt[i][j] = v[i];
continue;
}
spt[i][j] = spt[i][j-1];
if(i + (1LL << (j-1)) < n) spt[i][j] = max(spt[i][j-1], spt[i + (1LL << (j-1))][j-1]);
}
}
}
};
int rnd(){
return abs(int(rand() ^ (rand() << 3LL) ^ (rand() << 6LL)));
}
int biggest_stadium(int n, std::vector<std::vector<int>> f)
{
vector <vector<int>> A(n, vector <int> (n, 0)),
B(n, vector <int> (n, 0)),
C(n, vector <int> (n, 0)),
D(n, vector <int> (n, 0)),
T(n, vector <int> (n, 0));
vector <SPTMIN> sp1;
vector <SPTMAX> sp2;
cnt = 0;
for(int i = 1; i <= n; i++){
lg[i] = log2(i);
}
for(int i = 0; i < n; i++)
{
int last = -1;
for(int j = 0; j < n; j++){
if(f[i][j] == 1) last = j;
A[i][j] = last;
}
last = n;
for(int j = n-1; j >= 0; j--){
T[i][j] = last;
if(f[i][j] == 1) {
if(j != n-1 && last == j+1){
T[i][j] = T[i][j+1];
}else T[i][j] = j;
last = j;
}
B[i][j] = last;
}
}
for(int i = 0; i < n; i++)
{
int last = -1;
for(int j = 0; j < n; j++){
if(f[j][i] == 1) last = j;
C[j][i] = last+1;
}
last = n;
for(int j = n-1; j >= 0; j--){
if(f[j][i] == 1) last = j;
D[j][i] = last-1;
}
}
for(int i = 0; i < n; i++)
{
sp1.push_back(SPTMIN(D[i]));
sp2.push_back(SPTMAX(C[i]));
}
//return 0;
//vector <vector<vector<int>>> dp1(n + 1, vector <vector<int>>
// (n + 1, vector <int> (n + 1, -1)));
//vector <vector<vector<int>>> dp2(n + 1, vector <vector<int>>
// (n + 1, vector <int> (n + 1, -1)));
unordered_map <ll, int> dp;
auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int
{ cnt++;
long long x = ((ll) b) + (((ll) c) << 11LL) + (((ll) d) << 22LL) + (((ll) j) << 33LL)
+ (((ll) i) << 44LL) + (((ll) a) << 55LL);
if(dp[x] != 0) return dp[x];
dp[x] = (b - a + 1);
if(i != j) dp[x] += (d - c + 1);
int mx = 0;
if(i != 0)
{
for(int k = a; k <= b; k++) if(f[i-1][k] == 0)
{
int l1 = max(A[i-1][k]+1, a), r1 = min(B[i-1][k]-1, b);
int l2 = max(c, l1), r2 = min(d, r1);
int ni = sp2[i].query(l1, r1), d = abs(ni - i) - 1, t = (r1 - l1 + 1);
mx = max(mx, F(F, ni, j, l1, r1, l2, r2) - (r2 - l2 + 1) + d * t);
k = r1;
} else k = T[i-1][k];
}
if(j != n-1)
{
for(int k = c; k <= d; k++) if(f[j+1][k] == 0)
{
int l2 = max(A[j+1][k]+1, c), r2 = min(B[j+1][k]-1, d);
int l1 = max(a, l2), r1 = min(b, r2);
int nj = sp1[j].query(l2, r2), d = abs(nj - j) - 1, t = (r2 - l2 + 1);
mx = max(mx, F(F, i, nj, l1, r1, l2, r2) - (r1 - l1 + 1) + d * t);
k = r2;
} else k = T[j+1][k];
}
return dp[x] = (dp[x] + mx);
};
int ans = 0;
srand(time(NULL));
vector <pair<int, pair<int, int>>> fx;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(f[i][j] == 1) continue;
int l = A[i][j]+1, r = B[i][j]-1;
int ni = sp2[i].query(j, j);
int nj = sp1[i].query(j, j);
int d = r-l+1, h = (nj - ni + 1);
fx.push_back({ max(d, h), { i, j }});
}
}
sort(fx.begin(), fx.end());
while (fx.size() > 0)
{
pair<int, int> u = fx.back().second; fx.pop_back();
int i = u.first, j = u.second;
if(f[i][j] == 1) continue;
int l = A[i][j]+1, r = B[i][j]-1;
ans = max(ans, F(F, i, i, l, r, l, r));
if(n > 500 && cnt > TLE) {
break;
}
}
int mod = fx.size(); cnt = 0;
for(int i = 0; i < (int) fx.size(); i++){
int x = rnd() % mod;
swap(fx[i], fx[x]);
}
while (fx.size() > 0)
{
pair<int, int> u = fx.back().second; fx.pop_back();
int i = u.first, j = u.second;
if(f[i][j] == 1) continue;
int l = A[i][j]+1, r = B[i][j]-1;
ans = max(ans, F(F, i, i, l, r, l, r));
if(n > 500 && cnt > TLE) {
break;
}
}
return ans;
}
int main()
{
int N;
assert(1 == scanf("%d", &N));
std::vector<std::vector<int>> F(N, std::vector<int>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
assert(1 == scanf("%d", &F[i][j]));
}
}
fclose(stdin);
int res = biggest_stadium(N, F);
printf("%d\n", res);
fclose(stdout);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccZf31NO.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQ9jsML.o:soccer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
