#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int pref[N][N]={};
int go_down[N][N]={};
int go_up[N][N]={};
int go_right[N][N]={};
int go_left[N][N]={};
int streak_top[N]={};
int streak_bot[N]={};
int streak_left[N]={};
int streak_right[N]={};
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
pref[i][j] = F[i][j];
if (i>0)
pref[i][j] += pref[i-1][j];
if (j > 0)
pref[i][j] += pref[i][j-1];
if (i > 0 && j > 0)
pref[i][j] -= pref[i-1][j-1];
}
}
auto q = [&] (int i1, int j1, int i2, int j2) -> int {
int res = pref[i2][j2];
if (i1 > 0) res -= pref[i1-1][j2];
if (j1 > 0) res -= pref[i2][j1-1];
if (i1 > 0 && j1 > 0) res += pref[i1-1][j1-1];
return res;
};
for (int i = 0; i < N; ++i) {
go_left[i][0] = 0;
for (int j = 1; j < N; ++j) {
go_left[i][j] = (F[i][j-1] == 0 ? go_left[i][j-1] + 1 : 0);
}
go_right[i][N-1] = 0;
for (int j = N-2; j >= 0; --j) {
go_right[i][j] = (F[i][j+1] == 0 ? go_right[i][j+1] + 1 : 0);
}
go_up[0][i] = 0;
for (int j = 1; j < N; ++j) {
go_up[j][i] = (F[j-1][i] == 0 ? go_up[j-1][i] + 1 : 0);
}
go_down[N-1][i] = 0;
for (int j = N-2; j >= 0; --j) {
go_down[j][i] = (F[j+1][i] == 0 ? go_down[j+1][i] + 1 : 0);
}
}
auto solve_vert = [&] (int i1, int j1, int i2, int j2) -> int {
int add = 0;
int ret = 0;
for (int peak = j1; peak <= j2; ++peak) {
int tophere = go_up[i1][peak];
int bothere = go_down[i2][peak];
for (int j = peak-1; j >= j1; --j) {
if (streak_top[j] > tophere) {
add -= streak_top[j] - tophere;
streak_top[j] = tophere;
}
if (streak_bot[j] > bothere) {
add -= streak_bot[j] - bothere;
streak_bot[j] = bothere;
}
}
streak_top[peak] = tophere;
streak_bot[peak] = bothere;
add += tophere;
add += bothere;
ret = max(ret, add);
int here = add;
int ltop = streak_top[peak];
int lbot = streak_bot[peak];
for (int j = peak+1; j <= j2; ++j) {
int atop = go_up[i1][j];
int abot = go_down[i2][j];
ltop = min(atop, ltop);
lbot = min(abot, lbot);
here += ltop;
here += lbot;
ret = max(ret, here);
}
}
return ret;
};
auto solve_hor = [&] (int i1, int j1, int i2, int j2) -> int {
int add = 0;
int ret = 0;
for (int peak = i1; peak <= i2; ++peak) {
int left = go_left[peak][j1];
int right = go_right[peak][j2];
for (int i = peak-1; i >= i1; --i) {
if (streak_left[i] > left) {
add -= streak_left[i] - left;
streak_left[i] = left;
}
if (streak_right[i] > right) {
add -= streak_right[i] - right;
streak_right[i] = right;
}
}
streak_left[peak] = left;
streak_right[peak] = right;
add += left;
add += right;
ret = max(ret, add);
int here = add;
int lleft = streak_left[peak];
int lright = streak_right[peak];
for (int i = peak+1; i <= i2; ++i) {
int aleft = go_left[i][j1];
int aright = go_right[i][j2];
lleft = min(aleft, lleft);
lright = min(aright, lright);
here += lleft;
here += lright;
ret = max(ret, here);
}
}
return ret;
};
int res = 0;
for (int i1 = 0; i1 < N; ++i1) {
for (int j1 = 0; j1 < N; ++j1) {
for (int i2 = i1; i2 < N; ++i2) {
for (int j2 = j1; j2 < N; ++j2) {
if (q(i1, j1, i2, j2) > 0) continue;
int now = (i2-i1+1)*(j2-j1+1);
now += solve_hor(i1, j1, i2, j2);
now += solve_vert(i1, j1, i2, j2);
res = max(res, now);
}
}
}
}
return res;
}
| # |
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 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
344 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Execution timed out |
4599 ms |
348 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Incorrect |
0 ms |
348 KB |
wrong |
| 8 |
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 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Incorrect |
0 ms |
348 KB |
wrong |
| 9 |
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 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
344 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Incorrect |
0 ms |
348 KB |
wrong |
| 11 |
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 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
344 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Incorrect |
0 ms |
348 KB |
wrong |
| 11 |
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 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
344 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Execution timed out |
4599 ms |
348 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
