oj.uz

Submission #842412

# Submission time Handle Problem Language Result Execution time Memory
842412 2023-09-02T20:46:44 Z SHZhang Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 311 ms 112976 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 == 0) {
        return N * N;
    }
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 544 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 19 ms 2896 KB ok
9 Correct 239 ms 34060 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 2 ms 8536 KB ok
5 Correct 1 ms 8536 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8536 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8536 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 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 2 ms 8536 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 8536 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8536 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8536 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8536 KB ok
18 Correct 1 ms 8536 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8536 KB ok
21 Correct 1 ms 8536 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8536 KB ok
24 Correct 1 ms 8536 KB ok
25 Correct 1 ms 8536 KB ok
26 Correct 1 ms 8536 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 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 544 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 2 ms 8536 KB ok
8 Correct 1 ms 8536 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8536 KB ok
17 Correct 1 ms 8536 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8536 KB ok
21 Correct 1 ms 8536 KB ok
22 Correct 1 ms 8536 KB ok
23 Correct 1 ms 8536 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 1 ms 8536 KB ok
26 Correct 1 ms 8536 KB ok
27 Correct 1 ms 8536 KB ok
28 Correct 1 ms 8536 KB ok
29 Correct 1 ms 8536 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8540 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 8536 KB ok
34 Correct 1 ms 8536 KB ok
35 Correct 1 ms 8536 KB ok
36 Correct 1 ms 8536 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8536 KB ok
39 Correct 1 ms 8536 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8536 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 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 544 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 2 ms 8536 KB ok
8 Correct 1 ms 8536 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8536 KB ok
17 Correct 1 ms 8536 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8536 KB ok
21 Correct 1 ms 8536 KB ok
22 Correct 1 ms 8536 KB ok
23 Correct 1 ms 8536 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 1 ms 8536 KB ok
26 Correct 1 ms 8536 KB ok
27 Correct 1 ms 8536 KB ok
28 Correct 1 ms 8536 KB ok
29 Correct 1 ms 8536 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8540 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 8536 KB ok
34 Correct 1 ms 8536 KB ok
35 Correct 1 ms 8536 KB ok
36 Correct 1 ms 8536 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8536 KB ok
39 Correct 1 ms 8536 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8536 KB ok
42 Correct 194 ms 31824 KB ok
43 Correct 193 ms 31860 KB ok
44 Correct 214 ms 31860 KB ok
45 Correct 228 ms 31864 KB ok
46 Correct 193 ms 31832 KB ok
47 Correct 255 ms 31860 KB ok
48 Correct 211 ms 31856 KB ok
49 Correct 218 ms 31864 KB ok
50 Correct 221 ms 31844 KB ok
51 Correct 204 ms 31860 KB ok
52 Correct 191 ms 31860 KB ok
53 Correct 193 ms 31860 KB ok
54 Correct 203 ms 31832 KB ok
55 Correct 191 ms 31856 KB ok
56 Correct 204 ms 31636 KB ok
57 Correct 231 ms 31860 KB ok
58 Correct 231 ms 31860 KB ok
59 Correct 229 ms 31860 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 544 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 19 ms 2896 KB ok
10 Correct 239 ms 34060 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 2 ms 8536 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8536 KB ok
17 Correct 0 ms 348 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 8536 KB ok
22 Correct 1 ms 8536 KB ok
23 Correct 1 ms 8540 KB ok
24 Correct 1 ms 8536 KB ok
25 Correct 1 ms 8536 KB ok
26 Correct 1 ms 8536 KB ok
27 Correct 1 ms 8536 KB ok
28 Correct 1 ms 8536 KB ok
29 Correct 1 ms 8540 KB ok
30 Correct 1 ms 8536 KB ok
31 Correct 1 ms 8536 KB ok
32 Correct 1 ms 8536 KB ok
33 Correct 1 ms 8536 KB ok
34 Correct 1 ms 8536 KB ok
35 Correct 1 ms 8540 KB ok
36 Correct 1 ms 8540 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8536 KB ok
39 Correct 1 ms 8536 KB ok
40 Correct 1 ms 8536 KB ok
41 Correct 1 ms 8536 KB ok
42 Correct 1 ms 8540 KB ok
43 Correct 1 ms 8536 KB ok
44 Correct 1 ms 8536 KB ok
45 Correct 1 ms 8540 KB ok
46 Correct 1 ms 8536 KB ok
47 Correct 194 ms 31824 KB ok
48 Correct 193 ms 31860 KB ok
49 Correct 214 ms 31860 KB ok
50 Correct 228 ms 31864 KB ok
51 Correct 193 ms 31832 KB ok
52 Correct 255 ms 31860 KB ok
53 Correct 211 ms 31856 KB ok
54 Correct 218 ms 31864 KB ok
55 Correct 221 ms 31844 KB ok
56 Correct 204 ms 31860 KB ok
57 Correct 191 ms 31860 KB ok
58 Correct 193 ms 31860 KB ok
59 Correct 203 ms 31832 KB ok
60 Correct 191 ms 31856 KB ok
61 Correct 204 ms 31636 KB ok
62 Correct 231 ms 31860 KB ok
63 Correct 231 ms 31860 KB ok
64 Correct 229 ms 31860 KB ok
65 Partially correct 287 ms 112656 KB partial
66 Partially correct 311 ms 112720 KB partial
67 Partially correct 285 ms 112720 KB partial
68 Partially correct 270 ms 112720 KB partial
69 Partially correct 269 ms 112724 KB partial
70 Partially correct 270 ms 112720 KB partial
71 Partially correct 269 ms 112784 KB partial
72 Partially correct 287 ms 112660 KB partial
73 Correct 273 ms 112800 KB ok
74 Correct 272 ms 112784 KB ok
75 Correct 275 ms 112764 KB ok
76 Correct 280 ms 112720 KB ok
77 Partially correct 266 ms 112720 KB partial
78 Partially correct 287 ms 112644 KB partial
79 Partially correct 270 ms 112664 KB partial
80 Partially correct 284 ms 112792 KB partial
81 Partially correct 267 ms 112664 KB partial
82 Partially correct 268 ms 112660 KB partial
83 Partially correct 286 ms 112776 KB partial
84 Correct 268 ms 112832 KB ok
85 Correct 267 ms 112720 KB ok
86 Correct 264 ms 112720 KB ok
87 Correct 264 ms 112720 KB ok
88 Correct 263 ms 112660 KB ok
89 Correct 267 ms 112636 KB ok
90 Partially correct 263 ms 112576 KB partial
91 Partially correct 269 ms 112720 KB partial
92 Partially correct 287 ms 112976 KB partial
93 Partially correct 288 ms 112780 KB partial
94 Partially correct 293 ms 112620 KB partial
95 Partially correct 260 ms 112640 KB partial
96 Partially correct 267 ms 112720 KB partial
97 Partially correct 265 ms 112720 KB partial
98 Partially correct 258 ms 112724 KB partial
99 Correct 270 ms 112764 KB ok
100 Partially correct 272 ms 112672 KB partial
101 Correct 279 ms 112864 KB ok
102 Partially correct 274 ms 112720 KB partial
103 Partially correct 282 ms 112772 KB partial
104 Partially correct 268 ms 112716 KB partial
105 Partially correct 267 ms 112640 KB partial
106 Partially correct 265 ms 112640 KB partial
107 Correct 272 ms 112692 KB ok
108 Correct 274 ms 112660 KB ok
109 Partially correct 277 ms 112660 KB partial