oj.uz

Submission #842411

# Submission time Handle Problem Language Result Execution time Memory
842411 2023-09-02T20:45:39 Z SHZhang Soccer Stadium (IOI23_soccer) C++17
64 / 100
 241 ms 32596 KB 
#include "soccer.h"

#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int top[2005][2005];
int bottom[2005][2005];
int rangetop[2005][2005], rangebottom[2005][2005];
int f[2005][2005];

const int inf = -100000000;

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int trees = 0, x = 0, y = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                trees++;
                x = i; y = j;
            }
        }
    }
    if (trees == 1) {
        return N * N - min(x+1, N-x) * min(y+1, N-y);
    }
    int widest_row = -1;
    int widest_cnt = 0;
    for (int i = 0; i < N; i++) {
        int emptycnt = 0;
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                top[i][j] = N;
            } else if (i == 0 || F[i-1][j]) {
                top[i][j] = i; emptycnt++;
            } else {
                top[i][j] = top[i-1][j]; emptycnt++;
            }
        }
        if (emptycnt >= widest_cnt) {
            widest_row = i;
            widest_cnt = emptycnt;
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                bottom[i][j] = -1;
            } else if (i == N - 1 || F[i+1][j]) {
                bottom[i][j] = i;
            } else {
                bottom[i][j] = bottom[i+1][j];
            }
        }
    }
    int ans = 0;
    for (int mrow = 0; mrow < N; mrow++) {
        if (N > 500 && mrow != widest_row) continue;
        for (int i = 0; i < N; i++) {
            rangetop[i][i] = top[mrow][i];
            rangebottom[i][i] = bottom[mrow][i];
            f[i][i] = bottom[mrow][i] - top[mrow][i] + 1;
            if (f[i][i] < 0) f[i][i] = -inf;
        }
        for (int siz = 2; siz <= N; siz++) {
            for (int i = 0; i <= N - siz; i++) {
                rangetop[i][i+siz-1] = max(rangetop[i+1][i+siz-1], top[mrow][i]);
                rangebottom[i][i+siz-1] = min(rangebottom[i+1][i+siz-1], bottom[mrow][i]);
                if (rangetop[i][i+siz-1] > rangebottom[i][i+siz-1]) {
                    f[i][i+siz-1] = -inf;
                } else {
                    f[i][i+siz-1] = max(f[i+1][i+siz-1], f[i][i+siz-2]) + rangebottom[i][i+siz-1] - rangetop[i][i+siz-1] + 1;
                    ans = max(ans, f[i][i+siz-1]);
                }
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok

Subtask #1
0.0 / 6.0

# 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 Incorrect 1 ms 8536 KB wrong
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8536 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8544 KB ok
22 Correct 1 ms 8544 KB ok
23 Correct 1 ms 8544 KB ok
24 Correct 1 ms 8544 KB ok
25 Correct 1 ms 8544 KB ok
26 Correct 1 ms 8544 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 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 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8544 KB ok
24 Correct 1 ms 8544 KB ok
25 Correct 1 ms 8544 KB ok
26 Correct 1 ms 8544 KB ok
27 Correct 1 ms 8544 KB ok
28 Correct 1 ms 8544 KB ok
29 Correct 1 ms 8540 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8544 KB ok
32 Correct 1 ms 8544 KB ok
33 Correct 1 ms 8544 KB ok
34 Correct 1 ms 8540 KB ok
35 Correct 1 ms 8544 KB ok
36 Correct 1 ms 8540 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8540 KB ok
39 Correct 1 ms 8624 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8544 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 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 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8544 KB ok
24 Correct 1 ms 8544 KB ok
25 Correct 1 ms 8544 KB ok
26 Correct 1 ms 8544 KB ok
27 Correct 1 ms 8544 KB ok
28 Correct 1 ms 8544 KB ok
29 Correct 1 ms 8540 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8544 KB ok
32 Correct 1 ms 8544 KB ok
33 Correct 1 ms 8544 KB ok
34 Correct 1 ms 8540 KB ok
35 Correct 1 ms 8544 KB ok
36 Correct 1 ms 8540 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8540 KB ok
39 Correct 1 ms 8624 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8544 KB ok
42 Correct 198 ms 32348 KB ok
43 Correct 193 ms 32364 KB ok
44 Correct 217 ms 32352 KB ok
45 Correct 228 ms 32348 KB ok
46 Correct 192 ms 32340 KB ok
47 Correct 241 ms 32592 KB ok
48 Correct 206 ms 32352 KB ok
49 Correct 220 ms 32336 KB ok
50 Correct 224 ms 32596 KB ok
51 Correct 196 ms 32356 KB ok
52 Correct 186 ms 32344 KB ok
53 Correct 183 ms 32352 KB ok
54 Correct 190 ms 32352 KB ok
55 Correct 192 ms 32344 KB ok
56 Correct 210 ms 32352 KB ok
57 Correct 239 ms 32340 KB ok
58 Correct 221 ms 32348 KB ok
59 Correct 226 ms 32340 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 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 Incorrect 1 ms 8536 KB wrong
7 Halted 0 ms 0 KB -