//#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int biggest_stadium(int N, std::vector<std::vector<int>> C) {
vector<vector<int>> S(N);
auto fS = [&](int x, int y) {
if (x < 0 || y < 0) {
return 0;
}
if (x >= N) {
x = N - 1;
}
if (y >= N) {
y = N - 1;
}
return S[x][y];
};
auto sm = [&](int x1, int x2, int y1, int y2) -> int {
return fS(x2, y2) - fS(x1 - 1, y2) - fS(x2, y1 - 1) + fS(x1 - 1, y1 - 1);
};
for (int i = 0; i < N; i++) {
S[i] = vector<int>(N);
for (int j = 0; j < N; j++) {
S[i][j] = C[i][j];
S[i][j] += fS(i - 1, j) + fS(i, j - 1) - fS(i - 1, j - 1);
}
}
int best = 0;
vector<pair<pair<int, int>, pair<int, int>>> V;
function<void(int, int, int, int)> dfs = [&](int x1, int x2, int y1, int y2) -> void {
if (y1 > y2) {
return;
}
if (x2 != N - 1 && sm(x2 + 1, x2 + 1, y1, y2) == 0) {
return;
}
if (x1 == 0) {
V.push_back({{x1, x2},
{y1, y2}});
return;
}
if (sm(x1 - 1, x1 - 1, y1, y2) != 0) {
V.push_back({{x1, x2},
{y1, y2}});
}
int lst = y1 - 1;
for (int y = y1; y <= y2 + 1; y++) {
if (y == y2 + 1 || C[x1 - 1][y] == 1) {
dfs(x1 - 1, x2, lst + 1, y - 1);
lst = y;
}
}
};
for (int x = 0; x < N; x++) {
int lst = -1;
for (int y = 0; y <= N; y++) {
if (y == N || C[x][y] == 1) {
if (lst + 1 > y - 1) {
lst = y;
continue;
}
if (x != N - 1 && sm(x + 1, x + 1, lst + 1, y - 1) == 0) {
lst = y;
continue;
}
dfs(x, x, lst + 1, y - 1);
lst = y;
}
}
}
sort(V.begin(), V.end(),
[&](pair<pair<int, int>, pair<int, int>> a, pair<pair<int, int>, pair<int, int>> b) {
return a.second.second - a.second.first > b.second.second - b.second.first;
});
map<pair<pair<int, int>, pair<int, int>>, int> M;
auto check = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
auto [xp, yp] = i;
auto [x0, x1] = xp;
auto [y0, y1] = yp;
if (y0 > y1) {
return;
}
int lo = 0;
int hi = x0;
while (lo < hi) {
int m = (lo + hi) / 2;
if (sm(m, x0 - 1, y0, y1) == 0) {
hi = m;
} else {
lo = m + 1;
}
}
area += (y1 - y0 + 1) * (x0 - lo);
x0 = lo;
lo = x1;
hi = N - 1;
while (lo < hi) {
int m = (lo + hi + 1) / 2;
if (sm(x1 + 1, m, y0, y1) == 0) {
lo = m;
} else {
hi = m - 1;
}
}
area += (y1 - y0 + 1) * (lo - x1);
x1 = lo;
M[{{x0, x1},
{y0, y1}}] = max(M[{{x0, x1},
{y0, y1}}],
area);
};
auto expL = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
auto [xp, yp] = i;
auto [x0, x1] = xp;
auto [y0, y1] = yp;
if (y0 > y1) {
return;
}
int lst = y0 - 1;
for (int y = y0; y <= y1 + 1; y++) {
if (y == y1 + 1 || C[x0 - 1][y] == 1) {
check({{x0 - 1, x1},
{lst + 1, y - 1}}, area + (y - 1) - (lst + 1) + 1);
lst = y;
}
}
};
auto ones = [&](int x, int y0, int y1) -> vector<int> {
if (y0 > y1) {
return {};
}
vector<int> p;
while (y0 <= y1) {
if (sm(x, x, y0, y1) == 0) {
break;
}
int lo = y0;
int hi = y1;
while (lo < hi) {
int m = (lo + hi) / 2;
if (sm(x, x, y0, m) != 0) {
hi = m;
} else {
lo = m + 1;
}
p.push_back(lo);
y0 = lo + 1;
}
}
p.push_back(y1 + 1);
return p;
};
auto expR = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
auto [xp, yp] = i;
auto [x0, x1] = xp;
auto [y0, y1] = yp;
if (y0 > y1) {
return;
}
int lst = y0 - 1;
for (int y: ones(x1 + 1, y0, y1)) {
check({{x0, x1 + 1},
{lst + 1, y - 1}}, area + (y - 1) - (lst + 1) + 1);
lst = y;
}
};
for (auto i: V) {
auto [xp, yp] = i;
auto [x0, x1] = xp;
auto [y0, y1] = yp;
int dp = (x1 - x0 + 1) * (y1 - y0 + 1);
if (M.count(i)) {
dp = M[i];
} else {
M[i] = dp;
}
int ans = dp;
best = max(best, ans);
if (x0 != 0) {
expL(i, ans);
}
if (x1 != N - 1) {
expR(i, ans);
}
}
return best;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Incorrect |
1 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Incorrect |
1 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Incorrect |
1 ms |
344 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Incorrect |
1 ms |
344 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Incorrect |
1 ms |
344 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Incorrect |
1 ms |
344 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
