#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int dp[8000006];
int biggest_stadium(int N, vector<vector<int>> F) {
int n = N;
vector<vector<int>> a = F, next(n, vector<int>(n)), sum(n, vector<int>(n));
map<vector<int>, int> mp;
vector<vector<int>> v(n), vv;
function<int(int, int, int, int)> summ = [&] (int l, int r, int x, int y) {
long long ans = sum[y][r];
if (x - 1 >= 0) ans -= sum[x - 1][r];
if (l - 1 >= 0) ans -= sum[y][l - 1];
if (x - 1 >= 0 && l - 1 >= 0) ans += sum[x - 1][l - 1];
return ans;
};
int cnt = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
sum[i][j] += a[i][j];
if (j) sum[i][j] += sum[i][j - 1];
if (a[i][j] == 0) v[i].push_back(j);
}
v[i].push_back(n + 1);
}
for (int i = 1; i < n; i ++) {
for (int j = 0; j < n; j ++) sum[i][j] += sum[i - 1][j];
}
for (int i = 0; i < n; i ++) {
if (a[i][n - 1] == 0) next[i][n - 1] = n - 1;
else next[i][n - 1] = n - 2;
for (int j = n - 2; j >= 0; j --) {
if (a[i][j]) next[i][j] = j - 1;
else next[i][j] = next[i][j + 1];
}
}
int ans = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (a[i][j]) continue;
int ll = i, rr = n, mid, x, y;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, next[i][j], i, mid) == 0) ll = mid + 1;
else rr = mid;
}
ll --;
y = ll;
ll = 0, rr = i;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, next[i][j], mid, i) == 0) rr = mid;
else ll = mid + 1;
}
x = ll;
vector<int> vvv = {j, next[i][j], x, y};
if (mp[vvv] == 0) {
vv.push_back(vvv);
mp[vvv] = ++ cnt;
}
j = next[i][j];
}
}
function<bool(vector<int>, vector<int>)> cmp = [&](vector<int> a, vector<int> b) {
int siz1 = (a[1] - a[0] + 1), siz2 = (b[1] - b[0] + 1);
int siz3 = (a[3] - a[2] + 1), siz4 = (b[3] - b[2] + 1);
if (siz1 > siz2) return 1;
if (siz3 > siz4) return 1;
return 0;
};
sort(vv.begin(), vv.end(), cmp);
for (auto xx : vv) {
if (mp.count(xx) == 0) mp[xx] = ++ cnt;
int id = mp[xx];
dp[id] = max(dp[id], (xx[1] - xx[0] + 1) * (xx[3] - xx[2] + 1));
ans = max(ans, dp[id]);
int l = xx[0], r = xx[1], x = xx[2], y = xx[3];
if (x - 1 >= 0) {
for (int j = l; j <= r; j ++) {
int z = min(r, next[x - 1][j]);
if (a[x - 1][j] == 0) {
int ll = y, rr = n, mid, nx, ny;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, z, x, mid) == 0) ll = mid + 1;
else rr = mid;
}
ll --;
ny = ll;
ll = 0, rr = x;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, z, mid, y) == 0) rr = mid;
else ll = mid + 1;
}
nx = ll;
vector<int> xxx = {j, z, nx, ny};
if (mp.count(xxx) == 0) mp[xxx] = ++ cnt;
int idd = mp[xxx];
dp[idd] = max(dp[idd], dp[id] + (z - j + 1) * (x - nx + ny - y));
}
j = *upper_bound(v[x - 1].begin(), v[x - 1].end(), z) - 1;
}
}
if (y + 1 < n) {
for (int j = l; j <= r; j ++) {
int z = min(r, next[y + 1][j]);
if (a[y + 1][j] == 0) {
int ll = y, rr = n, mid, nx, ny;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, z, x, mid) == 0) ll = mid + 1;
else rr = mid;
}
ll --;
ny = ll;
ll = 0, rr = x;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, z, mid, y) == 0) rr = mid;
else ll = mid + 1;
}
nx = ll;
vector<int> xxx = {j, z, nx, ny};
if (mp.count(xxx) == 0) mp[xxx] = ++ cnt;
int idd = mp[xxx];
dp[idd] = max(dp[idd], dp[id] + (z - j + 1) * (x - nx + ny - y));
}
j = *upper_bound(v[y + 1].begin(), v[y + 1].end(), z) - 1;
}
}
}
return ans;
}
/*
3
0 0 0
0 1 0
0 0 0
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Incorrect |
1 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Incorrect |
1 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Incorrect |
1 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Incorrect |
1 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
