oj.uz

Submission #839750

# Submission time Handle Problem Language Result Execution time Memory
839750 2023-08-30T15:49:59 Z model_code Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2208 ms 793288 KB 
// model_solution/solution.cpp

#include "soccer.h"
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cassert>
const int MAXN = 3201;

template <int POW = 12>
struct sparse
{
    std::array<std::vector<int>, POW> dp;
    sparse(int N, int *t)
    {
        for (int i = 0; i < POW; ++i)
        {
            dp[i].resize(N);
        }

        for (int i = 0; i < N; ++i)
        {
            dp[0][i] = t[i];
        }

        for (int j = 1; j < POW; ++j)
        {
            for (int i = 0; i < N; ++i)
            {
                dp[j][i] = std::min(dp[j - 1][i], dp[j - 1][std::min(N - 1, i + (1 << (j - 1)))]);
            }
        }
    }

    int query(int x, int y)
    {
        int b = 31 - __builtin_clz(y - x + 1);
        return std::min(dp[b][x], dp[b][y - (1 << b) + 1]);
    }
};

class solver
{
    int N;
    std::vector<std::vector<int>> C;
    int nxt[2][MAXN][MAXN], prv[2][MAXN][MAXN];
    int up[MAXN][MAXN], down[MAXN][MAXN];
    std::vector<sparse<>> up_rmq, down_rmq;

    std::vector<std::array<int, 4>> rects;
    std::map<std::array<int, 4>, int> rect_to_ind;
    std::vector<int> dp;
    void gen_max_rectangles()
    {
        std::vector<std::array<int, 4>> stack; // (start, w, h, based)
        for (int i = 0; i < N; i++)
        {
            stack.clear();
            for (int j = 0; j <= N; j++)
            {
                int curr_h = j < N ? up[i][j] : 0;
                int curr_start = j, curr_w = 1;
                bool curr_based = i + 1 == N || C[i + 1][j];
                while (!stack.empty() && stack.back()[2] >= curr_h)
                {
                    auto [start, w, h, based] = stack.back();
                    curr_based |= based;
                    if (h > 0 && h != curr_h && curr_based)
                    {
                        rects.push_back({i - h + 1, start, i, start + w - 1 + curr_w - 1});
                        rect_to_ind[rects.back()] = (int)rects.size() - 1;
                    }

                    curr_start = start;
                    curr_w += w;

                    stack.pop_back();
                }

                stack.push_back({curr_start, curr_w, curr_h, curr_based});
            }
        }
        dp.assign(rects.size(), -1);
    }

    void init()
    {
        for (int i = 0; i < N; i++)
        {
            nxt[0][i][N - 1] = nxt[1][i][N - 1] = N;
            for (int j = N - 2; j >= 0; j--)
            {
                int nxt_elem = C[i][j + 1];

                nxt[nxt_elem][i][j] = j + 1;
                nxt[1 - nxt_elem][i][j] = nxt[1 - nxt_elem][i][j + 1];
            }

            prv[0][i][0] = prv[1][i][0] = -1;
            for (int j = 1; j < N; j++)
            {
                int prv_elem = C[i][j - 1];

                prv[prv_elem][i][j] = j - 1;
                prv[1 - prv_elem][i][j] = prv[1 - prv_elem][i][j - 1];
            }

            for (int j = 0; j < N; j++)
            {
                up[i][j] = (C[i][j] == 1 || i == 0) ? 1 - C[i][j] : 1 + up[i - 1][j];
                down[N - i - 1][j] = (C[N - i - 1][j] == 1 || i == 0) ? 1 - C[N - i - 1][j] : 1 + down[N - i][j];
            }
        }

        for (int i = 0; i < N; i++)
        {
            up_rmq.emplace_back(N, up[i]);
            down_rmq.emplace_back(N, down[i]);
        }
    }

    int query_up(int row, int l, int r)
    {
        return up_rmq[row].query(l, r);
    }
    int query_down(int row, int l, int r)
    {
        return down_rmq[row].query(l, r);
    }

    int calc(int ind)
    {
        if (dp[ind] != -1)
            return dp[ind];

        int a = rects[ind][0],
            b = rects[ind][1],
            c = rects[ind][2],
            d = rects[ind][3];

        int area = (c - a + 1) * (d - b + 1);
        int ans = area;

        if (a > 0)
        {
            int start = 0 == C[a - 1][b] ? b : nxt[0][a - 1][b];
            for (int i = start; i <= d;)
            {
                int until = std::min(nxt[1][a - 1][i] - 1, d);
                if (i == b && until == d)
                    break;
                // rmq
                int x = a - 1 - query_up(a - 1, i, until) + 1;
                int y = a - 1 + query_down(a - 1, i, until) - 1;

                if (rect_to_ind.count({x, i, y, until}))
                {
                    int to = rect_to_ind[{x, i, y, until}];
                    ans = std::max(ans, area + calc(to) - (c - a + 1) * (until - i + 1));
                }

                i = nxt[0][a - 1][until];
            }
        }

        if (c + 1 < N)
        {
            int start = 0 == C[c + 1][b] ? b : nxt[0][c + 1][b];
            for (int i = start; i <= d;)
            {
                int until = std::min(nxt[1][c + 1][i] - 1, d);
                if (i == b && until == d)
                    break;

                // rmq
                int x = c + 1 - query_up(c + 1, i, until) + 1;
                int y = c + 1 + query_down(c + 1, i, until) - 1;

                if (rect_to_ind.count({x, i, y, until}))
                {
                    int to = rect_to_ind[{x, i, y, until}];
                    ans = std::max(ans, area + calc(to) - (c - a + 1) * (until - i + 1));
                }

                i = nxt[0][c + 1][until];
            }
        }

        return dp[ind] = ans;
    }

public:
    solver(int size, std::vector<std::vector<int>> table) : N(size), C(std::move(table))
    {
        init();
        gen_max_rectangles();
    }

    int solve()
    {
        int ans = 0;
        for (int i = 0; i < (int)rects.size(); i++)
        {
            ans = std::max(ans, calc(i));
        }
        return ans;
    }
};

int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
    solver s(N, C);
    return s.solve();
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 240840 KB ok
2 Correct 87 ms 240824 KB ok
3 Correct 82 ms 240832 KB ok
4 Correct 83 ms 240856 KB ok
5 Correct 99 ms 240860 KB ok
6 Correct 80 ms 240792 KB ok
7 Correct 83 ms 241960 KB ok
8 Correct 127 ms 268088 KB ok
9 Correct 750 ms 671640 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 240840 KB ok
2 Correct 87 ms 240824 KB ok
3 Correct 88 ms 240844 KB ok
4 Correct 86 ms 240848 KB ok
5 Correct 85 ms 240812 KB ok
6 Correct 82 ms 240816 KB ok
7 Correct 95 ms 240848 KB ok
8 Correct 87 ms 240904 KB ok
9 Correct 85 ms 240792 KB ok
10 Correct 79 ms 240836 KB ok
11 Correct 99 ms 240860 KB ok
12 Correct 84 ms 240896 KB ok
13 Correct 84 ms 240900 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 240920 KB ok
2 Correct 97 ms 240840 KB ok
3 Correct 87 ms 240824 KB ok
4 Correct 88 ms 240844 KB ok
5 Correct 86 ms 240848 KB ok
6 Correct 85 ms 240812 KB ok
7 Correct 82 ms 240816 KB ok
8 Correct 95 ms 240848 KB ok
9 Correct 87 ms 240904 KB ok
10 Correct 85 ms 240792 KB ok
11 Correct 79 ms 240836 KB ok
12 Correct 99 ms 240860 KB ok
13 Correct 84 ms 240896 KB ok
14 Correct 84 ms 240900 KB ok
15 Correct 93 ms 240788 KB ok
16 Correct 84 ms 240892 KB ok
17 Correct 87 ms 240840 KB ok
18 Correct 97 ms 240900 KB ok
19 Correct 105 ms 240844 KB ok
20 Correct 80 ms 240840 KB ok
21 Correct 97 ms 240872 KB ok
22 Correct 86 ms 240912 KB ok
23 Correct 92 ms 240844 KB ok
24 Correct 84 ms 240852 KB ok
25 Correct 95 ms 240836 KB ok
26 Correct 103 ms 240808 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 240920 KB ok
2 Correct 97 ms 240840 KB ok
3 Correct 87 ms 240824 KB ok
4 Correct 82 ms 240832 KB ok
5 Correct 83 ms 240856 KB ok
6 Correct 88 ms 240844 KB ok
7 Correct 86 ms 240848 KB ok
8 Correct 85 ms 240812 KB ok
9 Correct 82 ms 240816 KB ok
10 Correct 95 ms 240848 KB ok
11 Correct 87 ms 240904 KB ok
12 Correct 85 ms 240792 KB ok
13 Correct 79 ms 240836 KB ok
14 Correct 99 ms 240860 KB ok
15 Correct 84 ms 240896 KB ok
16 Correct 84 ms 240900 KB ok
17 Correct 93 ms 240788 KB ok
18 Correct 84 ms 240892 KB ok
19 Correct 87 ms 240840 KB ok
20 Correct 97 ms 240900 KB ok
21 Correct 105 ms 240844 KB ok
22 Correct 80 ms 240840 KB ok
23 Correct 97 ms 240872 KB ok
24 Correct 86 ms 240912 KB ok
25 Correct 92 ms 240844 KB ok
26 Correct 84 ms 240852 KB ok
27 Correct 95 ms 240836 KB ok
28 Correct 103 ms 240808 KB ok
29 Correct 102 ms 240784 KB ok
30 Correct 96 ms 240972 KB ok
31 Correct 96 ms 241044 KB ok
32 Correct 98 ms 240944 KB ok
33 Correct 89 ms 240948 KB ok
34 Correct 102 ms 240968 KB ok
35 Correct 93 ms 240920 KB ok
36 Correct 103 ms 240980 KB ok
37 Correct 99 ms 241020 KB ok
38 Correct 90 ms 240952 KB ok
39 Correct 88 ms 240924 KB ok
40 Correct 95 ms 240976 KB ok
41 Correct 92 ms 241000 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 240920 KB ok
2 Correct 97 ms 240840 KB ok
3 Correct 87 ms 240824 KB ok
4 Correct 82 ms 240832 KB ok
5 Correct 83 ms 240856 KB ok
6 Correct 88 ms 240844 KB ok
7 Correct 86 ms 240848 KB ok
8 Correct 85 ms 240812 KB ok
9 Correct 82 ms 240816 KB ok
10 Correct 95 ms 240848 KB ok
11 Correct 87 ms 240904 KB ok
12 Correct 85 ms 240792 KB ok
13 Correct 79 ms 240836 KB ok
14 Correct 99 ms 240860 KB ok
15 Correct 84 ms 240896 KB ok
16 Correct 84 ms 240900 KB ok
17 Correct 93 ms 240788 KB ok
18 Correct 84 ms 240892 KB ok
19 Correct 87 ms 240840 KB ok
20 Correct 97 ms 240900 KB ok
21 Correct 105 ms 240844 KB ok
22 Correct 80 ms 240840 KB ok
23 Correct 97 ms 240872 KB ok
24 Correct 86 ms 240912 KB ok
25 Correct 92 ms 240844 KB ok
26 Correct 84 ms 240852 KB ok
27 Correct 95 ms 240836 KB ok
28 Correct 103 ms 240808 KB ok
29 Correct 102 ms 240784 KB ok
30 Correct 96 ms 240972 KB ok
31 Correct 96 ms 241044 KB ok
32 Correct 98 ms 240944 KB ok
33 Correct 89 ms 240948 KB ok
34 Correct 102 ms 240968 KB ok
35 Correct 93 ms 240920 KB ok
36 Correct 103 ms 240980 KB ok
37 Correct 99 ms 241020 KB ok
38 Correct 90 ms 240952 KB ok
39 Correct 88 ms 240924 KB ok
40 Correct 95 ms 240976 KB ok
41 Correct 92 ms 241000 KB ok
42 Correct 203 ms 273176 KB ok
43 Correct 198 ms 274896 KB ok
44 Correct 185 ms 269540 KB ok
45 Correct 159 ms 268820 KB ok
46 Correct 210 ms 271648 KB ok
47 Correct 140 ms 268180 KB ok
48 Correct 139 ms 268076 KB ok
49 Correct 151 ms 268252 KB ok
50 Correct 173 ms 273324 KB ok
51 Correct 147 ms 269640 KB ok
52 Correct 142 ms 268228 KB ok
53 Correct 134 ms 268236 KB ok
54 Correct 142 ms 268276 KB ok
55 Correct 138 ms 268216 KB ok
56 Correct 156 ms 268260 KB ok
57 Correct 180 ms 273556 KB ok
58 Correct 209 ms 274268 KB ok
59 Correct 186 ms 274936 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 240920 KB ok
2 Correct 97 ms 240840 KB ok
3 Correct 87 ms 240824 KB ok
4 Correct 82 ms 240832 KB ok
5 Correct 83 ms 240856 KB ok
6 Correct 99 ms 240860 KB ok
7 Correct 80 ms 240792 KB ok
8 Correct 83 ms 241960 KB ok
9 Correct 127 ms 268088 KB ok
10 Correct 750 ms 671640 KB ok
11 Correct 88 ms 240844 KB ok
12 Correct 86 ms 240848 KB ok
13 Correct 85 ms 240812 KB ok
14 Correct 82 ms 240816 KB ok
15 Correct 95 ms 240848 KB ok
16 Correct 87 ms 240904 KB ok
17 Correct 85 ms 240792 KB ok
18 Correct 79 ms 240836 KB ok
19 Correct 99 ms 240860 KB ok
20 Correct 84 ms 240896 KB ok
21 Correct 84 ms 240900 KB ok
22 Correct 93 ms 240788 KB ok
23 Correct 84 ms 240892 KB ok
24 Correct 87 ms 240840 KB ok
25 Correct 97 ms 240900 KB ok
26 Correct 105 ms 240844 KB ok
27 Correct 80 ms 240840 KB ok
28 Correct 97 ms 240872 KB ok
29 Correct 86 ms 240912 KB ok
30 Correct 92 ms 240844 KB ok
31 Correct 84 ms 240852 KB ok
32 Correct 95 ms 240836 KB ok
33 Correct 103 ms 240808 KB ok
34 Correct 102 ms 240784 KB ok
35 Correct 96 ms 240972 KB ok
36 Correct 96 ms 241044 KB ok
37 Correct 98 ms 240944 KB ok
38 Correct 89 ms 240948 KB ok
39 Correct 102 ms 240968 KB ok
40 Correct 93 ms 240920 KB ok
41 Correct 103 ms 240980 KB ok
42 Correct 99 ms 241020 KB ok
43 Correct 90 ms 240952 KB ok
44 Correct 88 ms 240924 KB ok
45 Correct 95 ms 240976 KB ok
46 Correct 92 ms 241000 KB ok
47 Correct 203 ms 273176 KB ok
48 Correct 198 ms 274896 KB ok
49 Correct 185 ms 269540 KB ok
50 Correct 159 ms 268820 KB ok
51 Correct 210 ms 271648 KB ok
52 Correct 140 ms 268180 KB ok
53 Correct 139 ms 268076 KB ok
54 Correct 151 ms 268252 KB ok
55 Correct 173 ms 273324 KB ok
56 Correct 147 ms 269640 KB ok
57 Correct 142 ms 268228 KB ok
58 Correct 134 ms 268236 KB ok
59 Correct 142 ms 268276 KB ok
60 Correct 138 ms 268216 KB ok
61 Correct 156 ms 268260 KB ok
62 Correct 180 ms 273556 KB ok
63 Correct 209 ms 274268 KB ok
64 Correct 186 ms 274936 KB ok
65 Correct 2099 ms 755304 KB ok
66 Correct 1178 ms 745536 KB ok
67 Correct 934 ms 699880 KB ok
68 Correct 800 ms 674544 KB ok
69 Correct 1268 ms 692356 KB ok
70 Correct 1666 ms 709008 KB ok
71 Correct 930 ms 671284 KB ok
72 Correct 836 ms 670104 KB ok
73 Correct 778 ms 671368 KB ok
74 Correct 773 ms 671012 KB ok
75 Correct 746 ms 670272 KB ok
76 Correct 1721 ms 752964 KB ok
77 Correct 1820 ms 751224 KB ok
78 Correct 927 ms 683712 KB ok
79 Correct 832 ms 676620 KB ok
80 Correct 925 ms 676516 KB ok
81 Correct 988 ms 675856 KB ok
82 Correct 864 ms 682308 KB ok
83 Correct 1133 ms 702472 KB ok
84 Correct 913 ms 669548 KB ok
85 Correct 709 ms 668248 KB ok
86 Correct 722 ms 669352 KB ok
87 Correct 730 ms 671572 KB ok
88 Correct 766 ms 669820 KB ok
89 Correct 727 ms 667500 KB ok
90 Correct 761 ms 668544 KB ok
91 Correct 816 ms 668828 KB ok
92 Correct 840 ms 685256 KB ok
93 Correct 1038 ms 694524 KB ok
94 Correct 803 ms 675040 KB ok
95 Correct 761 ms 670216 KB ok
96 Correct 750 ms 670116 KB ok
97 Correct 756 ms 670600 KB ok
98 Correct 759 ms 668984 KB ok
99 Correct 2208 ms 793288 KB ok
100 Correct 1568 ms 751224 KB ok
101 Correct 1492 ms 745960 KB ok
102 Correct 1576 ms 752544 KB ok
103 Correct 1746 ms 770956 KB ok
104 Correct 1946 ms 773764 KB ok
105 Correct 1873 ms 777712 KB ok
106 Correct 1962 ms 782568 KB ok
107 Correct 2069 ms 781380 KB ok
108 Correct 981 ms 726668 KB ok
109 Correct 1051 ms 729156 KB ok