#include <bits/stdc++.h>
using namespace std;
/*
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
what if the local maximum isn't strict? can we have another?
xx
xx
xxxxx
xxx
xxx
xx
yes we can
the stuff on top needs to also have this same pattern though
x
xx
xx
xxxxx
xxx
xxx
xx
like this is fine but it can't go down then up again
x x
xxx
xxx
xxxxx
xxx
xxx
xxx
we need to iterate through the heights of the local max now
and also the splitting point on the top
so now it's O(n^5)
how is this still failing wtf?
x
xx
xx
xxxxxx <- this is the backbone, then this is accounted for
xxxxxx
xxx
xxx
xx
let's just check that this is sufficient:
- from all nodes on the backbone, change column then row
- from all nodes on top, change row then column
- from all node below, if going to backbone change row then column
else if going to top change column then row
so I guess there must be some other extensions...
x
xxx
xxxxx
xxx
x
this isn't accounted for!
x
xxxx
xxxxxx
xxx
x
x
xxxx
xxxxxxxxx
xxxx
x
ok, if bottom and top maxima are not aligned then obviously gg
x
xxx
xxxx
xxxxxxxxxx
xxxxxxx
xx
i think let's consider taking two backbones, the row and the column
b
xbx
xxbx
bbbbbbbbbbb
xxbxxxx
xb
as long as the Xs are convex to the structure then yes it works
so let's do a dp[col][lo][hi][incr/decr][] : max area
as soon as one starts decr the other must as well
this dp is like O(n^4)
*/
const int MAXN = 30;
const int inf = 1 << 30;
int dp[MAXN][MAXN][MAXN][2];
int pre[MAXN + 1][MAXN];
void chmax(int &x, int y) {
x = max(x, y);
}
int biggest_stadium(int N, vector<vector<int>> F) {
// calc prefix sums
for (int col=0; col<N; col++) {
for (int row=0; row<N; row++) {
pre[row + 1][col] += pre[row][col];
pre[row + 1][col] += F[row][col];
}
}
// fill all with negative inf
for (int col=0; col<N; col++) {
for (int lo=0; lo<N; lo++) {
for (int hi=lo; hi<N; hi++) {
for (int f=0; f<2; f++) {
dp[col][lo][hi][f] = -inf;
}
}
}
}
// base case, col=0
for (int lo=0; lo<N; lo++) {
for (int hi=lo; hi<N; hi++) {
for (int f=0; f<2; f++) {
int ones = pre[hi + 1][0] - pre[lo][0];
if (ones == 0) {
dp[0][lo][hi][f] = hi - lo + 1;
}
}
}
}
// transition one col to the next
for (int col=0; col<N-1; col++) {
for (int lo=0; lo<N; lo++) {
for (int hi=lo; hi<N; hi++) {
if (dp[col][lo][hi][0] > 0) {
for (int lo2=lo; lo2>=0; lo2--) {
for (int hi2=hi; hi2<N; hi2++) {
int ones = pre[hi2 + 1][col + 1] - pre[lo2][col + 1];
if (ones > 0) break;
chmax(dp[col+1][lo2][hi2][0], dp[col][lo][hi][0] + hi2 - lo2 + 1);
chmax(dp[col+1][lo2][hi2][1], dp[col][lo][hi][0] + hi2 - lo2 + 1);
}
}
}
if (dp[col][lo][hi][1] > 0) {
for (int lo2=lo; lo2<N; lo2++) {
for (int hi2=hi; hi2>=lo2; hi2--) {
int ones = pre[hi2 + 1][col + 1] - pre[lo2][col + 1];
if (ones > 0) break;
chmax(dp[col+1][lo2][hi2][1], dp[col][lo][hi][1] + hi2 - lo2 + 1);
}
}
}
}
}
}
// get answer
int ans = 0;
for (int col=0; col<N; col++) {
for (int lo=0; lo<N; lo++) {
for (int hi=lo; hi<N; hi++) {
for (int f=0; f<2; f++) {
chmax(ans, dp[col][lo][hi][f]);
}
}
}
}
return ans;
}
/*
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 |
344 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
