oj.uz

Submission #839753

# Submission time Handle Problem Language Result Execution time Memory
839753 2023-08-30T15:50:06 Z model_code Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1000568 KB 
// correct/solution_slow.cpp

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

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, 3>> stack; // (start, w, h)
        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;
                while (!stack.empty() && stack.back()[2] >= curr_h)
                {
                    auto [start, w, h] = stack.back();
                    if (h > 0)
                    {
                        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});
            }
        }
        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 N, std::vector<std::vector<int>> C) : N(N), C(std::move(C))
    {
        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 95 ms 240964 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 241044 KB ok
2 Correct 96 ms 241016 KB ok
3 Correct 96 ms 241036 KB ok
4 Correct 86 ms 241052 KB ok
5 Correct 113 ms 241052 KB ok
6 Correct 94 ms 240960 KB ok
7 Correct 104 ms 242964 KB ok
8 Correct 191 ms 288764 KB ok
9 Correct 2309 ms 1000568 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 241044 KB ok
2 Correct 96 ms 241016 KB ok
3 Correct 94 ms 240956 KB ok
4 Correct 98 ms 240936 KB ok
5 Correct 106 ms 241044 KB ok
6 Correct 120 ms 241056 KB ok
7 Correct 93 ms 241004 KB ok
8 Correct 95 ms 240996 KB ok
9 Correct 105 ms 240968 KB ok
10 Correct 92 ms 241028 KB ok
11 Correct 88 ms 241032 KB ok
12 Correct 84 ms 240988 KB ok
13 Correct 77 ms 241040 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 240964 KB ok
2 Correct 105 ms 241044 KB ok
3 Correct 96 ms 241016 KB ok
4 Correct 94 ms 240956 KB ok
5 Correct 98 ms 240936 KB ok
6 Correct 106 ms 241044 KB ok
7 Correct 120 ms 241056 KB ok
8 Correct 93 ms 241004 KB ok
9 Correct 95 ms 240996 KB ok
10 Correct 105 ms 240968 KB ok
11 Correct 92 ms 241028 KB ok
12 Correct 88 ms 241032 KB ok
13 Correct 84 ms 240988 KB ok
14 Correct 77 ms 241040 KB ok
15 Correct 77 ms 241016 KB ok
16 Correct 98 ms 241036 KB ok
17 Correct 120 ms 241008 KB ok
18 Correct 117 ms 241036 KB ok
19 Correct 135 ms 240980 KB ok
20 Correct 98 ms 241124 KB ok
21 Correct 102 ms 240972 KB ok
22 Correct 81 ms 240944 KB ok
23 Correct 79 ms 241032 KB ok
24 Correct 73 ms 240972 KB ok
25 Correct 109 ms 241048 KB ok
26 Correct 103 ms 240956 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 240964 KB ok
2 Correct 105 ms 241044 KB ok
3 Correct 96 ms 241016 KB ok
4 Correct 96 ms 241036 KB ok
5 Correct 86 ms 241052 KB ok
6 Correct 94 ms 240956 KB ok
7 Correct 98 ms 240936 KB ok
8 Correct 106 ms 241044 KB ok
9 Correct 120 ms 241056 KB ok
10 Correct 93 ms 241004 KB ok
11 Correct 95 ms 240996 KB ok
12 Correct 105 ms 240968 KB ok
13 Correct 92 ms 241028 KB ok
14 Correct 88 ms 241032 KB ok
15 Correct 84 ms 240988 KB ok
16 Correct 77 ms 241040 KB ok
17 Correct 77 ms 241016 KB ok
18 Correct 98 ms 241036 KB ok
19 Correct 120 ms 241008 KB ok
20 Correct 117 ms 241036 KB ok
21 Correct 135 ms 240980 KB ok
22 Correct 98 ms 241124 KB ok
23 Correct 102 ms 240972 KB ok
24 Correct 81 ms 240944 KB ok
25 Correct 79 ms 241032 KB ok
26 Correct 73 ms 240972 KB ok
27 Correct 109 ms 241048 KB ok
28 Correct 103 ms 240956 KB ok
29 Correct 103 ms 240960 KB ok
30 Correct 90 ms 241196 KB ok
31 Correct 86 ms 241228 KB ok
32 Correct 89 ms 241172 KB ok
33 Correct 82 ms 241104 KB ok
34 Correct 92 ms 241100 KB ok
35 Correct 93 ms 241232 KB ok
36 Correct 129 ms 241160 KB ok
37 Correct 101 ms 241100 KB ok
38 Correct 102 ms 241104 KB ok
39 Correct 150 ms 241100 KB ok
40 Correct 86 ms 241232 KB ok
41 Correct 73 ms 241160 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 240964 KB ok
2 Correct 105 ms 241044 KB ok
3 Correct 96 ms 241016 KB ok
4 Correct 96 ms 241036 KB ok
5 Correct 86 ms 241052 KB ok
6 Correct 94 ms 240956 KB ok
7 Correct 98 ms 240936 KB ok
8 Correct 106 ms 241044 KB ok
9 Correct 120 ms 241056 KB ok
10 Correct 93 ms 241004 KB ok
11 Correct 95 ms 240996 KB ok
12 Correct 105 ms 240968 KB ok
13 Correct 92 ms 241028 KB ok
14 Correct 88 ms 241032 KB ok
15 Correct 84 ms 240988 KB ok
16 Correct 77 ms 241040 KB ok
17 Correct 77 ms 241016 KB ok
18 Correct 98 ms 241036 KB ok
19 Correct 120 ms 241008 KB ok
20 Correct 117 ms 241036 KB ok
21 Correct 135 ms 240980 KB ok
22 Correct 98 ms 241124 KB ok
23 Correct 102 ms 240972 KB ok
24 Correct 81 ms 240944 KB ok
25 Correct 79 ms 241032 KB ok
26 Correct 73 ms 240972 KB ok
27 Correct 109 ms 241048 KB ok
28 Correct 103 ms 240956 KB ok
29 Correct 103 ms 240960 KB ok
30 Correct 90 ms 241196 KB ok
31 Correct 86 ms 241228 KB ok
32 Correct 89 ms 241172 KB ok
33 Correct 82 ms 241104 KB ok
34 Correct 92 ms 241100 KB ok
35 Correct 93 ms 241232 KB ok
36 Correct 129 ms 241160 KB ok
37 Correct 101 ms 241100 KB ok
38 Correct 102 ms 241104 KB ok
39 Correct 150 ms 241100 KB ok
40 Correct 86 ms 241232 KB ok
41 Correct 73 ms 241160 KB ok
42 Correct 283 ms 286856 KB ok
43 Correct 272 ms 284664 KB ok
44 Correct 380 ms 288716 KB ok
45 Correct 488 ms 288660 KB ok
46 Correct 315 ms 287928 KB ok
47 Correct 261 ms 288916 KB ok
48 Correct 230 ms 278532 KB ok
49 Correct 224 ms 280560 KB ok
50 Correct 4242 ms 283724 KB ok
51 Correct 276 ms 285992 KB ok
52 Correct 153 ms 271312 KB ok
53 Correct 113 ms 269468 KB ok
54 Correct 164 ms 271048 KB ok
55 Correct 183 ms 272664 KB ok
56 Correct 155 ms 276792 KB ok
57 Correct 297 ms 289052 KB ok
58 Correct 451 ms 288904 KB ok
59 Correct 324 ms 288844 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 240964 KB ok
2 Correct 105 ms 241044 KB ok
3 Correct 96 ms 241016 KB ok
4 Correct 96 ms 241036 KB ok
5 Correct 86 ms 241052 KB ok
6 Correct 113 ms 241052 KB ok
7 Correct 94 ms 240960 KB ok
8 Correct 104 ms 242964 KB ok
9 Correct 191 ms 288764 KB ok
10 Correct 2309 ms 1000568 KB ok
11 Correct 94 ms 240956 KB ok
12 Correct 98 ms 240936 KB ok
13 Correct 106 ms 241044 KB ok
14 Correct 120 ms 241056 KB ok
15 Correct 93 ms 241004 KB ok
16 Correct 95 ms 240996 KB ok
17 Correct 105 ms 240968 KB ok
18 Correct 92 ms 241028 KB ok
19 Correct 88 ms 241032 KB ok
20 Correct 84 ms 240988 KB ok
21 Correct 77 ms 241040 KB ok
22 Correct 77 ms 241016 KB ok
23 Correct 98 ms 241036 KB ok
24 Correct 120 ms 241008 KB ok
25 Correct 117 ms 241036 KB ok
26 Correct 135 ms 240980 KB ok
27 Correct 98 ms 241124 KB ok
28 Correct 102 ms 240972 KB ok
29 Correct 81 ms 240944 KB ok
30 Correct 79 ms 241032 KB ok
31 Correct 73 ms 240972 KB ok
32 Correct 109 ms 241048 KB ok
33 Correct 103 ms 240956 KB ok
34 Correct 103 ms 240960 KB ok
35 Correct 90 ms 241196 KB ok
36 Correct 86 ms 241228 KB ok
37 Correct 89 ms 241172 KB ok
38 Correct 82 ms 241104 KB ok
39 Correct 92 ms 241100 KB ok
40 Correct 93 ms 241232 KB ok
41 Correct 129 ms 241160 KB ok
42 Correct 101 ms 241100 KB ok
43 Correct 102 ms 241104 KB ok
44 Correct 150 ms 241100 KB ok
45 Correct 86 ms 241232 KB ok
46 Correct 73 ms 241160 KB ok
47 Correct 283 ms 286856 KB ok
48 Correct 272 ms 284664 KB ok
49 Correct 380 ms 288716 KB ok
50 Correct 488 ms 288660 KB ok
51 Correct 315 ms 287928 KB ok
52 Correct 261 ms 288916 KB ok
53 Correct 230 ms 278532 KB ok
54 Correct 224 ms 280560 KB ok
55 Correct 4242 ms 283724 KB ok
56 Correct 276 ms 285992 KB ok
57 Correct 153 ms 271312 KB ok
58 Correct 113 ms 269468 KB ok
59 Correct 164 ms 271048 KB ok
60 Correct 183 ms 272664 KB ok
61 Correct 155 ms 276792 KB ok
62 Correct 297 ms 289052 KB ok
63 Correct 451 ms 288904 KB ok
64 Correct 324 ms 288844 KB ok
65 Execution timed out 4555 ms 965980 KB Time limit exceeded
66 Halted 0 ms 0 KB -