#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 = 4e6;
#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()
{
int ans = rand();
return (ans ^ (ans << 5) ^ (ans << 15));
}
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--){
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]));
}
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, int>> fx;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
fx.push_back({ i, j });
}
}
int mod = (int) fx.size();
for(int i = 0; i < (int) fx.size(); i++){
int x = rnd() % mod;
swap(fx[i], fx[x]);
}
for(auto& u : fx)
{
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) {
return ans;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
