oj.uz

답안 #1078585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078585 2024-08-27T21:51:47 Z myst6 축구 경기장 (IOI23_soccer) C++17
13.5 / 100
 4500 ms 58392 KB 
#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

*/

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 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 -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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

Subtask #3
5.5 / 22.0

# 결과 실행 시간 메모리 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

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 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 -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 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 -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 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 -