oj.uz

Submission #840861

# Submission time Handle Problem Language Result Execution time Memory
840861 2023-08-31T19:19:59 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
100 / 100
 4399 ms 1151512 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 2e3+10, L = 12;
 
struct Sparse {
    int sparse[L][M];
    Sparse() {}
    Sparse(vector<int>& v) {
        int n = v.size();
        for (int j = 0; j < n; j++) sparse[0][j] = v[j];
        for (int i = 1; (1 << i) <= n; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]);
            }
        }
    }
 
    inline int qry(int l, int r) {
        int b = 31 - __builtin_clz(r - l + 1);
        return min(sparse[b][l], sparse[b][r - (1 << b) + 1]);
    }
} ones[M], twos[M];
 
int get_cost(int i, int l, int r) {
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}

int cnt_lr[M][M], cnt_l[M][M], cnt_r[M][M];
int store_up[M][M], store_down[M][M];
basic_string<pair<int, int>> impl[M][M], impr[M][M], has[M][M];
int dp[2 * M * M];
ar<int, 3> all[2 * M * M];
 
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    for (int j = 0; j < N; j++) {
        int one = 0;
        for (int i = 0; i < N; i++) {
            one = F[i][j] ? 0 : one + 1;
            store_up[i][j] = one;
        }

        int two = 0;
        for (int i = N-1; i >= 0; i--) {
            two = F[i][j] ? 0 : two + 1;
            store_down[i][j] = two;
        }
    }

    for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            up[j] = store_up[i][j], down[j] = store_down[i][j];
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
    }
 
    int id = 0;
    auto add_imp = [&](int i, int l, int r) {
        all[id++] = {i, l, r};
        cnt_lr[l][r]++;
        cnt_l[i][l]++, cnt_r[i][r]++;
    };
 
    for (int i = 0; i < N; i++) {
        vector<int> blocks{-1};
        for (int j = 0; j < N; j++) if (F[i][j])
            blocks.push_back(j);
        
        blocks.push_back(N);
 
        for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) {
            int l = blocks[j-1]+1, r = blocks[j]-1;
            for (int k = l; k <= r; k++) {
                add_imp(i, k, r);
                if (k != r) add_imp(i, l, k);
            }
        }
    }
 
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        impl[i][j].reserve(cnt_l[i][j]), impr[i][j].reserve(cnt_r[i][j]);
        has[i][j].reserve(cnt_lr[i][j]);
    }

    for (int me = 0; me < id; me++) {
        auto [i, l, r] = all[me];
        has[l][r].push_back(make_pair(i, me));
    }

    for (int l = 0; l < N; l++) {
        for (int r = 0; r < N; r++) {
            for (auto [i, me] : has[l][r]) {
                impl[i][l].push_back(make_pair(r, me));
            }
        }
    }

    for (int r = 0; r < N; r++) {
        for (int l = 0; l < N; l++) {
            for (auto [i, me] : has[l][r]) {
                impr[i][r].push_back(make_pair(l, me));
            }
        }
    }

    auto upd = [&](int ni, int l, int r, int x, int cur_cost) {
        if (ni < 0 || ni >= N) return;
        int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), make_pair(l, M)) - impr[ni][r].begin();
        if (nl < sz(impr[ni][r])) {
            int id = impr[ni][r][nl].second;
            nl = impr[ni][r][nl].first;
            dp[id] = max(dp[id], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1));
        }
 
        int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), make_pair(r, -1)) - impl[ni][l].begin() - 1;
        if (nr >= 0) {
            int id = impl[ni][l][nr].second;
            nr = impl[ni][l][nr].first;
            dp[id] = max(dp[id], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };
 
    for (int l = 0; l < N; l++) {
        for (int r = N-1; r >= 0; r--) {
            for (auto [i, id] : has[l][r]) {
                int cur_cost = get_cost(i, l, r);
                int store = dp[id] = max(dp[id], cur_cost * (r - l + 1));
 
                int top = i - ones[i].qry(l, r);
                int bot = i + twos[i].qry(l, r);
                upd(i, l, r, store, cur_cost);
                upd(top, l, r, store, cur_cost);
                upd(bot, l, r, store, cur_cost);
            }
        }
    }
 
    int ans = 0;
    for (auto& x : dp) ans = max(ans, x);
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 380616 KB ok
2 Correct 161 ms 380700 KB ok
3 Correct 151 ms 381916 KB ok
4 Correct 152 ms 382152 KB ok
5 Correct 155 ms 380368 KB ok
6 Correct 149 ms 380620 KB ok
7 Correct 162 ms 401708 KB ok
8 Correct 293 ms 506188 KB ok
9 Correct 2671 ms 1112972 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 380616 KB ok
2 Correct 161 ms 380700 KB ok
3 Correct 163 ms 380584 KB ok
4 Correct 154 ms 380648 KB ok
5 Correct 151 ms 380664 KB ok
6 Correct 151 ms 380668 KB ok
7 Correct 152 ms 380620 KB ok
8 Correct 151 ms 380684 KB ok
9 Correct 152 ms 380688 KB ok
10 Correct 153 ms 380804 KB ok
11 Correct 153 ms 380620 KB ok
12 Correct 156 ms 380592 KB ok
13 Correct 158 ms 380620 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 381104 KB ok
2 Correct 150 ms 380616 KB ok
3 Correct 161 ms 380700 KB ok
4 Correct 163 ms 380584 KB ok
5 Correct 154 ms 380648 KB ok
6 Correct 151 ms 380664 KB ok
7 Correct 151 ms 380668 KB ok
8 Correct 152 ms 380620 KB ok
9 Correct 151 ms 380684 KB ok
10 Correct 152 ms 380688 KB ok
11 Correct 153 ms 380804 KB ok
12 Correct 153 ms 380620 KB ok
13 Correct 156 ms 380592 KB ok
14 Correct 158 ms 380620 KB ok
15 Correct 157 ms 381528 KB ok
16 Correct 158 ms 381520 KB ok
17 Correct 152 ms 381516 KB ok
18 Correct 152 ms 381516 KB ok
19 Correct 151 ms 381484 KB ok
20 Correct 157 ms 381516 KB ok
21 Correct 151 ms 381516 KB ok
22 Correct 152 ms 381484 KB ok
23 Correct 154 ms 381408 KB ok
24 Correct 150 ms 381420 KB ok
25 Correct 150 ms 381516 KB ok
26 Correct 150 ms 381516 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 381104 KB ok
2 Correct 150 ms 380616 KB ok
3 Correct 161 ms 380700 KB ok
4 Correct 151 ms 381916 KB ok
5 Correct 152 ms 382152 KB ok
6 Correct 163 ms 380584 KB ok
7 Correct 154 ms 380648 KB ok
8 Correct 151 ms 380664 KB ok
9 Correct 151 ms 380668 KB ok
10 Correct 152 ms 380620 KB ok
11 Correct 151 ms 380684 KB ok
12 Correct 152 ms 380688 KB ok
13 Correct 153 ms 380804 KB ok
14 Correct 153 ms 380620 KB ok
15 Correct 156 ms 380592 KB ok
16 Correct 158 ms 380620 KB ok
17 Correct 157 ms 381528 KB ok
18 Correct 158 ms 381520 KB ok
19 Correct 152 ms 381516 KB ok
20 Correct 152 ms 381516 KB ok
21 Correct 151 ms 381484 KB ok
22 Correct 157 ms 381516 KB ok
23 Correct 151 ms 381516 KB ok
24 Correct 152 ms 381484 KB ok
25 Correct 154 ms 381408 KB ok
26 Correct 150 ms 381420 KB ok
27 Correct 150 ms 381516 KB ok
28 Correct 150 ms 381516 KB ok
29 Correct 151 ms 381560 KB ok
30 Correct 153 ms 386404 KB ok
31 Correct 158 ms 386336 KB ok
32 Correct 153 ms 386284 KB ok
33 Correct 154 ms 386264 KB ok
34 Correct 157 ms 386368 KB ok
35 Correct 154 ms 386252 KB ok
36 Correct 154 ms 386124 KB ok
37 Correct 161 ms 386124 KB ok
38 Correct 168 ms 386120 KB ok
39 Correct 155 ms 386124 KB ok
40 Correct 157 ms 386212 KB ok
41 Correct 160 ms 386632 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 381104 KB ok
2 Correct 150 ms 380616 KB ok
3 Correct 161 ms 380700 KB ok
4 Correct 151 ms 381916 KB ok
5 Correct 152 ms 382152 KB ok
6 Correct 163 ms 380584 KB ok
7 Correct 154 ms 380648 KB ok
8 Correct 151 ms 380664 KB ok
9 Correct 151 ms 380668 KB ok
10 Correct 152 ms 380620 KB ok
11 Correct 151 ms 380684 KB ok
12 Correct 152 ms 380688 KB ok
13 Correct 153 ms 380804 KB ok
14 Correct 153 ms 380620 KB ok
15 Correct 156 ms 380592 KB ok
16 Correct 158 ms 380620 KB ok
17 Correct 157 ms 381528 KB ok
18 Correct 158 ms 381520 KB ok
19 Correct 152 ms 381516 KB ok
20 Correct 152 ms 381516 KB ok
21 Correct 151 ms 381484 KB ok
22 Correct 157 ms 381516 KB ok
23 Correct 151 ms 381516 KB ok
24 Correct 152 ms 381484 KB ok
25 Correct 154 ms 381408 KB ok
26 Correct 150 ms 381420 KB ok
27 Correct 150 ms 381516 KB ok
28 Correct 150 ms 381516 KB ok
29 Correct 151 ms 381560 KB ok
30 Correct 153 ms 386404 KB ok
31 Correct 158 ms 386336 KB ok
32 Correct 153 ms 386284 KB ok
33 Correct 154 ms 386264 KB ok
34 Correct 157 ms 386368 KB ok
35 Correct 154 ms 386252 KB ok
36 Correct 154 ms 386124 KB ok
37 Correct 161 ms 386124 KB ok
38 Correct 168 ms 386120 KB ok
39 Correct 155 ms 386124 KB ok
40 Correct 157 ms 386212 KB ok
41 Correct 160 ms 386632 KB ok
42 Correct 315 ms 505036 KB ok
43 Correct 309 ms 503200 KB ok
44 Correct 350 ms 507600 KB ok
45 Correct 370 ms 507860 KB ok
46 Correct 332 ms 506248 KB ok
47 Correct 305 ms 506316 KB ok
48 Correct 243 ms 498384 KB ok
49 Correct 253 ms 498892 KB ok
50 Correct 262 ms 499980 KB ok
51 Correct 283 ms 504396 KB ok
52 Correct 217 ms 488436 KB ok
53 Correct 208 ms 485512 KB ok
54 Correct 219 ms 488144 KB ok
55 Correct 220 ms 491172 KB ok
56 Correct 266 ms 493804 KB ok
57 Correct 295 ms 508420 KB ok
58 Correct 298 ms 508548 KB ok
59 Correct 299 ms 508632 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 381104 KB ok
2 Correct 150 ms 380616 KB ok
3 Correct 161 ms 380700 KB ok
4 Correct 151 ms 381916 KB ok
5 Correct 152 ms 382152 KB ok
6 Correct 155 ms 380368 KB ok
7 Correct 149 ms 380620 KB ok
8 Correct 162 ms 401708 KB ok
9 Correct 293 ms 506188 KB ok
10 Correct 2671 ms 1112972 KB ok
11 Correct 163 ms 380584 KB ok
12 Correct 154 ms 380648 KB ok
13 Correct 151 ms 380664 KB ok
14 Correct 151 ms 380668 KB ok
15 Correct 152 ms 380620 KB ok
16 Correct 151 ms 380684 KB ok
17 Correct 152 ms 380688 KB ok
18 Correct 153 ms 380804 KB ok
19 Correct 153 ms 380620 KB ok
20 Correct 156 ms 380592 KB ok
21 Correct 158 ms 380620 KB ok
22 Correct 157 ms 381528 KB ok
23 Correct 158 ms 381520 KB ok
24 Correct 152 ms 381516 KB ok
25 Correct 152 ms 381516 KB ok
26 Correct 151 ms 381484 KB ok
27 Correct 157 ms 381516 KB ok
28 Correct 151 ms 381516 KB ok
29 Correct 152 ms 381484 KB ok
30 Correct 154 ms 381408 KB ok
31 Correct 150 ms 381420 KB ok
32 Correct 150 ms 381516 KB ok
33 Correct 150 ms 381516 KB ok
34 Correct 151 ms 381560 KB ok
35 Correct 153 ms 386404 KB ok
36 Correct 158 ms 386336 KB ok
37 Correct 153 ms 386284 KB ok
38 Correct 154 ms 386264 KB ok
39 Correct 157 ms 386368 KB ok
40 Correct 154 ms 386252 KB ok
41 Correct 154 ms 386124 KB ok
42 Correct 161 ms 386124 KB ok
43 Correct 168 ms 386120 KB ok
44 Correct 155 ms 386124 KB ok
45 Correct 157 ms 386212 KB ok
46 Correct 160 ms 386632 KB ok
47 Correct 315 ms 505036 KB ok
48 Correct 309 ms 503200 KB ok
49 Correct 350 ms 507600 KB ok
50 Correct 370 ms 507860 KB ok
51 Correct 332 ms 506248 KB ok
52 Correct 305 ms 506316 KB ok
53 Correct 243 ms 498384 KB ok
54 Correct 253 ms 498892 KB ok
55 Correct 262 ms 499980 KB ok
56 Correct 283 ms 504396 KB ok
57 Correct 217 ms 488436 KB ok
58 Correct 208 ms 485512 KB ok
59 Correct 219 ms 488144 KB ok
60 Correct 220 ms 491172 KB ok
61 Correct 266 ms 493804 KB ok
62 Correct 295 ms 508420 KB ok
63 Correct 298 ms 508548 KB ok
64 Correct 299 ms 508632 KB ok
65 Correct 3320 ms 1091508 KB ok
66 Correct 1244 ms 915404 KB ok
67 Correct 932 ms 872908 KB ok
68 Correct 4399 ms 1135616 KB ok
69 Correct 4197 ms 1123772 KB ok
70 Correct 3854 ms 1114688 KB ok
71 Correct 4022 ms 1127504 KB ok
72 Correct 2979 ms 1115508 KB ok
73 Correct 1630 ms 1000652 KB ok
74 Correct 1635 ms 1002700 KB ok
75 Correct 1648 ms 1001896 KB ok
76 Correct 2130 ms 1010836 KB ok
77 Correct 2207 ms 1014028 KB ok
78 Correct 2672 ms 1100168 KB ok
79 Correct 908 ms 873360 KB ok
80 Correct 969 ms 874044 KB ok
81 Correct 1039 ms 890032 KB ok
82 Correct 1368 ms 926632 KB ok
83 Correct 1217 ms 910272 KB ok
84 Correct 924 ms 861080 KB ok
85 Correct 866 ms 848268 KB ok
86 Correct 1010 ms 876640 KB ok
87 Correct 1097 ms 882040 KB ok
88 Correct 1587 ms 944108 KB ok
89 Correct 2275 ms 1088140 KB ok
90 Correct 1900 ms 1032300 KB ok
91 Correct 2345 ms 1081056 KB ok
92 Correct 995 ms 888580 KB ok
93 Correct 1033 ms 883320 KB ok
94 Correct 956 ms 880012 KB ok
95 Correct 945 ms 883172 KB ok
96 Correct 940 ms 883724 KB ok
97 Correct 943 ms 884024 KB ok
98 Correct 849 ms 871560 KB ok
99 Correct 2732 ms 1099916 KB ok
100 Correct 2817 ms 1147632 KB ok
101 Correct 2777 ms 1143156 KB ok
102 Correct 2851 ms 1147736 KB ok
103 Correct 2813 ms 1150152 KB ok
104 Correct 2820 ms 1150868 KB ok
105 Correct 2823 ms 1151332 KB ok
106 Correct 2797 ms 1151512 KB ok
107 Correct 2797 ms 1149332 KB ok
108 Correct 2325 ms 1091176 KB ok
109 Correct 2314 ms 1092920 KB ok