Submission #1078606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078606		myst6	Soccer Stadium (IOI23_soccer)	C++17	30 / 100	4573 ms	4700 KiB

soccer

#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

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
 xxx
 xxx
xxxxx
 xxx
 xx
 x

*/

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
            for (int h=1; h<=down[i][j]; h++) {
                // choose its height down below to be h
                int ans = h;
                // go left on bottom
                int L = j;
                {
                    int curr = h;
                    for (int k=j-1; k>=0; k--) {
                        if (F[i][k] == 1) break;
                        curr = min(curr, down[i][k]);
                        ans += curr;
                        if (curr == h) L = k;
                    }
                }
                // go right on bottom
                int R = j;
                {
                    int curr = h;
                    for (int k=j+1; k<N; k++) {
                        if (F[i][k] == 1) break;
                        curr = min(curr, down[i][k]);
                        ans += curr;
                        if (curr == h) R = k;
                    }
                }
                // choose splitting point on top to be j2
                int best2 = 0;
                for (int j2=L; j2<=R; j2++) {
                    int ans2 = up[i][j2] - 1;
                    // go left on top
                    {
                        int curr = up[i][j2];
                        for (int k=j2-1; k>=L; k--) {
                            if (F[i][k] == 1) break;
                            curr = min(curr, up[i][k]);
                            ans2 += curr - 1;
                        }
                    }
                    // go right on top
                    {
                        int curr = up[i][j2];
                        for (int k=j2+1; k<=R; k++) {
                            if (F[i][k] == 1) break;
                            curr = min(curr, up[i][k]);
                            ans2 += curr - 1;
                        }
                    }
                    best2 = max(best2, ans2);
                }
                ans += best2;
                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

*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30