#include <bits/stdc++.h>
using namespace std;
bool dp[4][2005][2005];
/*
let's consider the bottom edge
we must be able to reach all other cells with an up kick then left kick
a rectangle is a valid field because yes
if any two filled positions on same row or col have a tree between them then no
if we fill in all empty spaces and consider that whole square
we see that the trees form either strict decreasing or strict increasing thingies
xx..
xxx.
.xxx
..xx
still bad
consider top-left one
it needs to either have access to all rows or all cols
xxxx
xxxx
.xxx
..xx
now good
xxxx
.xxx
..xx
....
still good
so, one side needs to be completely filled in
if we can solve where the top side is completely full, then rotate 90deg 4 times
xxxx
.xxx
..xx
...x
now, restriction on rest is?
it must be increasing then decreasing section
xxxxxxxx
.xxxxx.x
..xxx..x
...xx..x
let's say we have down[i][j] : how far down we can go from here
for a given row, let's say position k is the local maximum
then we do a greedy on both sides to calculate scores
so O(n^2) per row
so O(n^3) in total
where does this account for something like
x
x
xxxxx
x
x
x
xxx
xxxxx
x
x
I think in addition to the backbone and stalagmites we can have one prong upwards
xxxxx
xxx
xx
x
x
x
xxxxx
xxx
xx
x
i think the prong needs to be above the splitting point, too
otherwise, there's a column we can't reach
*/
const int MAXN = 2000;
int down[MAXN][MAXN];
int up[MAXN][MAXN];
int solve(int N, vector<vector<int>> F) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
// go as far down as possible in O(n^3)
for (int k=i; k<N; k++) {
if (F[k][j] == 1) break;
down[i][j] = k-i+1;
}
// go as far up as possible in O(n^3)
for (int k=i; k>=0; k--) {
if (F[k][j] == 1) break;
up[i][j] = i-k+1;
}
}
}
int best = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (F[i][j] == 1) continue;
// choose position (i, j) as the splitting point on row i
int ans = down[i][j] + up[i][j] - 1;
// go left
{
int curr = down[i][j];
for (int k=j-1; k>=0; k--) {
if (F[i][k] == 1) break;
curr = min(curr, down[i][k]);
ans += curr;
}
}
// go right
{
int curr = down[i][j];
for (int k=j+1; k<N; k++) {
if (F[i][k] == 1) break;
curr = min(curr, down[i][k]);
ans += curr;
}
}
best = max(best, ans);
}
}
return best;
}
vector<vector<int>> rotate(int N, vector<vector<int>> F) {
vector<vector<int>> G(N, vector<int>(N));
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
G[i][j] = F[N-1-j][i];
}
}
return G;
}
int biggest_stadium(int N, vector<vector<int>> F) {
int best = 0;
for (int i=0; i<4; i++) {
best = max(best, solve(N, F));
F = rotate(N, F);
}
return best;
}
/*
5
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
344 KB |
ok |
| 3 |
Correct |
1 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
7 ms |
1372 KB |
ok |
| 8 |
Correct |
882 ms |
10828 KB |
ok |
| 9 |
Execution timed out |
4550 ms |
58392 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
344 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
344 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
348 KB |
ok |
| 15 |
Correct |
0 ms |
348 KB |
ok |
| 16 |
Correct |
0 ms |
348 KB |
ok |
| 17 |
Partially correct |
0 ms |
348 KB |
partial |
| 18 |
Correct |
0 ms |
348 KB |
ok |
| 19 |
Correct |
0 ms |
348 KB |
ok |
| 20 |
Correct |
1 ms |
344 KB |
ok |
| 21 |
Correct |
1 ms |
344 KB |
ok |
| 22 |
Correct |
1 ms |
348 KB |
ok |
| 23 |
Correct |
0 ms |
348 KB |
ok |
| 24 |
Correct |
0 ms |
440 KB |
ok |
| 25 |
Partially correct |
0 ms |
348 KB |
partial |
| 26 |
Correct |
1 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
344 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
344 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
344 KB |
ok |
| 15 |
Correct |
0 ms |
348 KB |
ok |
| 16 |
Correct |
0 ms |
348 KB |
ok |
| 17 |
Correct |
0 ms |
348 KB |
ok |
| 18 |
Correct |
0 ms |
348 KB |
ok |
| 19 |
Partially correct |
0 ms |
348 KB |
partial |
| 20 |
Correct |
0 ms |
348 KB |
ok |
| 21 |
Correct |
0 ms |
348 KB |
ok |
| 22 |
Correct |
1 ms |
344 KB |
ok |
| 23 |
Correct |
1 ms |
344 KB |
ok |
| 24 |
Correct |
1 ms |
348 KB |
ok |
| 25 |
Correct |
0 ms |
348 KB |
ok |
| 26 |
Correct |
0 ms |
440 KB |
ok |
| 27 |
Partially correct |
0 ms |
348 KB |
partial |
| 28 |
Correct |
1 ms |
348 KB |
ok |
| 29 |
Correct |
0 ms |
348 KB |
ok |
| 30 |
Correct |
1 ms |
604 KB |
ok |
| 31 |
Correct |
1 ms |
604 KB |
ok |
| 32 |
Correct |
1 ms |
604 KB |
ok |
| 33 |
Correct |
1 ms |
600 KB |
ok |
| 34 |
Incorrect |
1 ms |
604 KB |
wrong |
| 35 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
344 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
344 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
344 KB |
ok |
| 15 |
Correct |
0 ms |
348 KB |
ok |
| 16 |
Correct |
0 ms |
348 KB |
ok |
| 17 |
Correct |
0 ms |
348 KB |
ok |
| 18 |
Correct |
0 ms |
348 KB |
ok |
| 19 |
Partially correct |
0 ms |
348 KB |
partial |
| 20 |
Correct |
0 ms |
348 KB |
ok |
| 21 |
Correct |
0 ms |
348 KB |
ok |
| 22 |
Correct |
1 ms |
344 KB |
ok |
| 23 |
Correct |
1 ms |
344 KB |
ok |
| 24 |
Correct |
1 ms |
348 KB |
ok |
| 25 |
Correct |
0 ms |
348 KB |
ok |
| 26 |
Correct |
0 ms |
440 KB |
ok |
| 27 |
Partially correct |
0 ms |
348 KB |
partial |
| 28 |
Correct |
1 ms |
348 KB |
ok |
| 29 |
Correct |
0 ms |
348 KB |
ok |
| 30 |
Correct |
1 ms |
604 KB |
ok |
| 31 |
Correct |
1 ms |
604 KB |
ok |
| 32 |
Correct |
1 ms |
604 KB |
ok |
| 33 |
Correct |
1 ms |
600 KB |
ok |
| 34 |
Incorrect |
1 ms |
604 KB |
wrong |
| 35 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
344 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
7 ms |
1372 KB |
ok |
| 9 |
Correct |
882 ms |
10828 KB |
ok |
| 10 |
Execution timed out |
4550 ms |
58392 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
