oj.uz

Submission #1033196

# Submission time Handle Problem Language Result Execution time Memory
1033196 2024-07-24T14:05:15 Z TAhmed33 Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1466 ms 335604 KB 
#include "soccer.h"
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e3 + 25;
const int M = (1 << 30) - 1;
const int B = 1e5 + 4;
int n, a[MAXN][MAXN], pref[MAXN][MAXN], pre[MAXN][MAXN];
int sparse[MAXN][11][MAXN];
int query (int x1, int y1, int x2, int y2) {
    return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}
struct custom_hash {
    size_t operator()(array <int, 4> x) const {
        return ((x[0] + x[1] * B + x[2] * B * B + x[3] * B * B * B) % M + M) % M;
    }
};
unordered_map <array <int, 4>, int, custom_hash> memo;
int query (int j, int l, int r) {
    int x = __lg(r - l + 1);
    return min(sparse[j][x][l], sparse[j][x][r - (1 << x) + 1]);
}
int get (int l, int r, int x, int y) {
    int R = r;
    int ans = r + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (query(x, mid, R) < y) {
            l = mid + 1;
        } else {
            r = mid - 1; ans = mid;
        }
    }
    return ans;
}
int get2 (int l, int r, int x, int y) {
    int L = l;
    int ans = l - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (query(x, L, mid) < y) {
            r = mid - 1;
        } else {
            l = mid + 1; ans = mid;
        }
    }
    return ans;
}
int ans (int x, int y, int l, int r) {
    if (memo.count({x, y, l, r})) {
        return memo[{x, y, l, r}];
    }
    int ret = 0;
    for (int i = l; i <= r; i++) {
        if (x != 1 && !a[x - 1][i]) {
            if (i > l && !a[x - 1][i - 1]) {
                continue;
            }
            int j = min(r + 1, pre[x - 1][i]);
            int g = get(1, x - 1, i, j);
            int h = get2(y + 1, n, i, j);
            ret = max(ret, (j - i) * (x - g + h - y) + ans(g, h, i, j - 1));
            i = j;
        }
    }
    for (int i = l; i <= r; i++) {
        if (y != n && !a[y + 1][i]) {
            if (i > l && !a[y + 1][i - 1]) {
                continue;
            }
            int j = min(r + 1, pre[y + 1][i]);
            int g = get(1, x - 1, i, j);
            int h = get2(y + 1, n, i, j);
            ret = max(ret, (j - i) * (x - g + h - y) + ans(g, h, i, j - 1));
            i = j;
        }
    }
    return memo[{x, y, l, r}] = ret;
}
int biggest_stadium (int _N, vector <vector <int>> _F) {
    //start with explaining the 25% solution
    n = _N;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = _F[i - 1][j - 1];
            pref[i][j] = a[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        int z = n + 1;
        for (int j = n; j >= 1; j--) {
            if (a[i][j]) {
                z = j;
            }
            pre[i][j] = z;
        }
    }
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            sparse[j][0][i] = pre[i][j];
        }
        for (int k = 1; k < 11; k++) {
            for (int i = 1; i + (1 << k) - 1 <= n; i++) {
                sparse[j][k][i] = min(sparse[j][k - 1][i], sparse[j][k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j]) {
                continue;
            }
            if (j > 1 && !a[i][j - 1]) {
                continue;
            }
            ret = max(ret, (pre[i][j] - j) + ans(i, i, j, pre[i][j] - 1));
        }
    }
    return ret;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.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 1 ms 604 KB ok
4 Correct 0 ms 700 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 2 ms 4700 KB ok
8 Correct 27 ms 37724 KB ok
9 Correct 296 ms 261428 KB ok

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 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 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 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 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 412 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 1 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 1 ms 600 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 700 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 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 412 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 1 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 1 ms 600 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 1372 KB ok
31 Correct 1 ms 1372 KB ok
32 Correct 1 ms 1372 KB ok
33 Correct 1 ms 1372 KB ok
34 Correct 1 ms 1372 KB ok
35 Correct 1 ms 1372 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1372 KB ok
38 Correct 1 ms 1368 KB ok
39 Correct 1 ms 1372 KB ok
40 Correct 1 ms 1372 KB ok
41 Correct 1 ms 1372 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 700 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 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 412 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 1 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 1 ms 600 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 1372 KB ok
31 Correct 1 ms 1372 KB ok
32 Correct 1 ms 1372 KB ok
33 Correct 1 ms 1372 KB ok
34 Correct 1 ms 1372 KB ok
35 Correct 1 ms 1372 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1372 KB ok
38 Correct 1 ms 1368 KB ok
39 Correct 1 ms 1372 KB ok
40 Correct 1 ms 1372 KB ok
41 Correct 1 ms 1372 KB ok
42 Correct 90 ms 41316 KB ok
43 Correct 79 ms 43620 KB ok
44 Correct 37 ms 38552 KB ok
45 Correct 38 ms 38152 KB ok
46 Correct 58 ms 40732 KB ok
47 Correct 28 ms 37720 KB ok
48 Correct 27 ms 37656 KB ok
49 Correct 26 ms 37712 KB ok
50 Correct 71 ms 41292 KB ok
51 Correct 35 ms 39348 KB ok
52 Correct 26 ms 37716 KB ok
53 Correct 26 ms 37720 KB ok
54 Correct 27 ms 37644 KB ok
55 Correct 27 ms 37712 KB ok
56 Correct 26 ms 37720 KB ok
57 Correct 50 ms 41316 KB ok
58 Correct 52 ms 41716 KB ok
59 Correct 56 ms 42332 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 700 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 2 ms 4700 KB ok
9 Correct 27 ms 37724 KB ok
10 Correct 296 ms 261428 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 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 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 1 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 412 KB ok
26 Correct 0 ms 604 KB ok
27 Correct 1 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 0 ms 604 KB ok
31 Correct 0 ms 604 KB ok
32 Correct 0 ms 604 KB ok
33 Correct 1 ms 600 KB ok
34 Correct 0 ms 604 KB ok
35 Correct 1 ms 1372 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1372 KB ok
38 Correct 1 ms 1372 KB ok
39 Correct 1 ms 1372 KB ok
40 Correct 1 ms 1372 KB ok
41 Correct 1 ms 1372 KB ok
42 Correct 1 ms 1372 KB ok
43 Correct 1 ms 1368 KB ok
44 Correct 1 ms 1372 KB ok
45 Correct 1 ms 1372 KB ok
46 Correct 1 ms 1372 KB ok
47 Correct 90 ms 41316 KB ok
48 Correct 79 ms 43620 KB ok
49 Correct 37 ms 38552 KB ok
50 Correct 38 ms 38152 KB ok
51 Correct 58 ms 40732 KB ok
52 Correct 28 ms 37720 KB ok
53 Correct 27 ms 37656 KB ok
54 Correct 26 ms 37712 KB ok
55 Correct 71 ms 41292 KB ok
56 Correct 35 ms 39348 KB ok
57 Correct 26 ms 37716 KB ok
58 Correct 26 ms 37720 KB ok
59 Correct 27 ms 37644 KB ok
60 Correct 27 ms 37712 KB ok
61 Correct 26 ms 37720 KB ok
62 Correct 50 ms 41316 KB ok
63 Correct 52 ms 41716 KB ok
64 Correct 56 ms 42332 KB ok
65 Correct 1466 ms 321860 KB ok
66 Correct 910 ms 323584 KB ok
67 Correct 465 ms 286072 KB ok
68 Correct 365 ms 264368 KB ok
69 Correct 644 ms 275916 KB ok
70 Correct 902 ms 287604 KB ok
71 Correct 341 ms 262932 KB ok
72 Correct 297 ms 261460 KB ok
73 Correct 326 ms 261736 KB ok
74 Correct 351 ms 261392 KB ok
75 Correct 329 ms 261536 KB ok
76 Correct 1442 ms 319840 KB ok
77 Correct 1343 ms 319732 KB ok
78 Correct 473 ms 276644 KB ok
79 Correct 456 ms 268484 KB ok
80 Correct 401 ms 267360 KB ok
81 Correct 410 ms 267468 KB ok
82 Correct 433 ms 270084 KB ok
83 Correct 807 ms 289984 KB ok
84 Correct 355 ms 261388 KB ok
85 Correct 356 ms 261528 KB ok
86 Correct 384 ms 261660 KB ok
87 Correct 359 ms 262484 KB ok
88 Correct 350 ms 261456 KB ok
89 Correct 288 ms 261664 KB ok
90 Correct 445 ms 261648 KB ok
91 Correct 349 ms 261432 KB ok
92 Correct 485 ms 276088 KB ok
93 Correct 513 ms 279928 KB ok
94 Correct 474 ms 267460 KB ok
95 Correct 353 ms 264432 KB ok
96 Correct 334 ms 263148 KB ok
97 Correct 353 ms 262896 KB ok
98 Correct 338 ms 261972 KB ok
99 Correct 1200 ms 327404 KB ok
100 Correct 997 ms 320240 KB ok
101 Correct 864 ms 315644 KB ok
102 Correct 894 ms 320216 KB ok
103 Correct 1144 ms 328100 KB ok
104 Correct 1034 ms 331004 KB ok
105 Correct 940 ms 333344 KB ok
106 Correct 1143 ms 335604 KB ok
107 Correct 1107 ms 335368 KB ok
108 Correct 719 ms 294140 KB ok
109 Correct 868 ms 294264 KB ok