oj.uz

Submission #839759

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

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

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<std::array<int, 4>> rects;
    std::map<std::array<int, 4>, int> rect_to_ind;
    std::vector<int> dp;
    void gen_max_rectangles()
    {
        for (int i = 0; i < N; i++)
        {
            std::vector<std::array<int, 3>> stack; // (start, w, h)
            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];
            }
        }
    }

    int query_up(int row, int l, int r)
    {
        return *std::min_element(up[row] + l, up[row] + r + 1);
    }
    int query_down(int row, int l, int r)
    {
        return *std::min_element(down[row] + l, down[row] + r + 1);
    }

    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 79 ms 240980 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 240988 KB ok
2 Correct 101 ms 240980 KB ok
3 Correct 95 ms 241036 KB ok
4 Correct 114 ms 240972 KB ok
5 Correct 108 ms 240988 KB ok
6 Correct 112 ms 241084 KB ok
7 Correct 128 ms 241904 KB ok
8 Correct 178 ms 264576 KB ok
9 Correct 1725 ms 616912 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 240988 KB ok
2 Correct 101 ms 240980 KB ok
3 Correct 105 ms 240960 KB ok
4 Correct 75 ms 240992 KB ok
5 Correct 73 ms 240948 KB ok
6 Correct 93 ms 241036 KB ok
7 Correct 73 ms 240924 KB ok
8 Correct 80 ms 240996 KB ok
9 Correct 76 ms 240972 KB ok
10 Correct 79 ms 240932 KB ok
11 Correct 78 ms 240972 KB ok
12 Correct 85 ms 240940 KB ok
13 Correct 94 ms 240972 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 240980 KB ok
2 Correct 96 ms 240988 KB ok
3 Correct 101 ms 240980 KB ok
4 Correct 105 ms 240960 KB ok
5 Correct 75 ms 240992 KB ok
6 Correct 73 ms 240948 KB ok
7 Correct 93 ms 241036 KB ok
8 Correct 73 ms 240924 KB ok
9 Correct 80 ms 240996 KB ok
10 Correct 76 ms 240972 KB ok
11 Correct 79 ms 240932 KB ok
12 Correct 78 ms 240972 KB ok
13 Correct 85 ms 240940 KB ok
14 Correct 94 ms 240972 KB ok
15 Correct 85 ms 241012 KB ok
16 Correct 84 ms 241036 KB ok
17 Correct 74 ms 240996 KB ok
18 Correct 118 ms 241052 KB ok
19 Correct 109 ms 241016 KB ok
20 Correct 100 ms 240984 KB ok
21 Correct 92 ms 240980 KB ok
22 Correct 89 ms 240960 KB ok
23 Correct 103 ms 241032 KB ok
24 Correct 101 ms 241036 KB ok
25 Correct 110 ms 241024 KB ok
26 Correct 98 ms 241012 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 240980 KB ok
2 Correct 96 ms 240988 KB ok
3 Correct 101 ms 240980 KB ok
4 Correct 95 ms 241036 KB ok
5 Correct 114 ms 240972 KB ok
6 Correct 105 ms 240960 KB ok
7 Correct 75 ms 240992 KB ok
8 Correct 73 ms 240948 KB ok
9 Correct 93 ms 241036 KB ok
10 Correct 73 ms 240924 KB ok
11 Correct 80 ms 240996 KB ok
12 Correct 76 ms 240972 KB ok
13 Correct 79 ms 240932 KB ok
14 Correct 78 ms 240972 KB ok
15 Correct 85 ms 240940 KB ok
16 Correct 94 ms 240972 KB ok
17 Correct 85 ms 241012 KB ok
18 Correct 84 ms 241036 KB ok
19 Correct 74 ms 240996 KB ok
20 Correct 118 ms 241052 KB ok
21 Correct 109 ms 241016 KB ok
22 Correct 100 ms 240984 KB ok
23 Correct 92 ms 240980 KB ok
24 Correct 89 ms 240960 KB ok
25 Correct 103 ms 241032 KB ok
26 Correct 101 ms 241036 KB ok
27 Correct 110 ms 241024 KB ok
28 Correct 98 ms 241012 KB ok
29 Correct 94 ms 240976 KB ok
30 Correct 99 ms 241112 KB ok
31 Correct 116 ms 241092 KB ok
32 Correct 99 ms 241084 KB ok
33 Correct 87 ms 240948 KB ok
34 Correct 90 ms 241024 KB ok
35 Correct 110 ms 240996 KB ok
36 Correct 101 ms 240984 KB ok
37 Correct 111 ms 241056 KB ok
38 Correct 95 ms 240964 KB ok
39 Correct 99 ms 241076 KB ok
40 Correct 94 ms 241100 KB ok
41 Correct 99 ms 241120 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 240980 KB ok
2 Correct 96 ms 240988 KB ok
3 Correct 101 ms 240980 KB ok
4 Correct 95 ms 241036 KB ok
5 Correct 114 ms 240972 KB ok
6 Correct 105 ms 240960 KB ok
7 Correct 75 ms 240992 KB ok
8 Correct 73 ms 240948 KB ok
9 Correct 93 ms 241036 KB ok
10 Correct 73 ms 240924 KB ok
11 Correct 80 ms 240996 KB ok
12 Correct 76 ms 240972 KB ok
13 Correct 79 ms 240932 KB ok
14 Correct 78 ms 240972 KB ok
15 Correct 85 ms 240940 KB ok
16 Correct 94 ms 240972 KB ok
17 Correct 85 ms 241012 KB ok
18 Correct 84 ms 241036 KB ok
19 Correct 74 ms 240996 KB ok
20 Correct 118 ms 241052 KB ok
21 Correct 109 ms 241016 KB ok
22 Correct 100 ms 240984 KB ok
23 Correct 92 ms 240980 KB ok
24 Correct 89 ms 240960 KB ok
25 Correct 103 ms 241032 KB ok
26 Correct 101 ms 241036 KB ok
27 Correct 110 ms 241024 KB ok
28 Correct 98 ms 241012 KB ok
29 Correct 94 ms 240976 KB ok
30 Correct 99 ms 241112 KB ok
31 Correct 116 ms 241092 KB ok
32 Correct 99 ms 241084 KB ok
33 Correct 87 ms 240948 KB ok
34 Correct 90 ms 241024 KB ok
35 Correct 110 ms 240996 KB ok
36 Correct 101 ms 240984 KB ok
37 Correct 111 ms 241056 KB ok
38 Correct 95 ms 240964 KB ok
39 Correct 99 ms 241076 KB ok
40 Correct 94 ms 241100 KB ok
41 Correct 99 ms 241120 KB ok
42 Correct 297 ms 262488 KB ok
43 Correct 257 ms 260420 KB ok
44 Correct 390 ms 264284 KB ok
45 Correct 369 ms 264460 KB ok
46 Correct 319 ms 263588 KB ok
47 Correct 165 ms 264488 KB ok
48 Correct 215 ms 254316 KB ok
49 Correct 197 ms 256272 KB ok
50 Correct 3481 ms 259428 KB ok
51 Correct 248 ms 261788 KB ok
52 Correct 137 ms 247128 KB ok
53 Correct 127 ms 245160 KB ok
54 Correct 153 ms 246692 KB ok
55 Correct 166 ms 248512 KB ok
56 Correct 170 ms 252288 KB ok
57 Correct 357 ms 264584 KB ok
58 Correct 396 ms 264520 KB ok
59 Correct 398 ms 264592 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 240980 KB ok
2 Correct 96 ms 240988 KB ok
3 Correct 101 ms 240980 KB ok
4 Correct 95 ms 241036 KB ok
5 Correct 114 ms 240972 KB ok
6 Correct 108 ms 240988 KB ok
7 Correct 112 ms 241084 KB ok
8 Correct 128 ms 241904 KB ok
9 Correct 178 ms 264576 KB ok
10 Correct 1725 ms 616912 KB ok
11 Correct 105 ms 240960 KB ok
12 Correct 75 ms 240992 KB ok
13 Correct 73 ms 240948 KB ok
14 Correct 93 ms 241036 KB ok
15 Correct 73 ms 240924 KB ok
16 Correct 80 ms 240996 KB ok
17 Correct 76 ms 240972 KB ok
18 Correct 79 ms 240932 KB ok
19 Correct 78 ms 240972 KB ok
20 Correct 85 ms 240940 KB ok
21 Correct 94 ms 240972 KB ok
22 Correct 85 ms 241012 KB ok
23 Correct 84 ms 241036 KB ok
24 Correct 74 ms 240996 KB ok
25 Correct 118 ms 241052 KB ok
26 Correct 109 ms 241016 KB ok
27 Correct 100 ms 240984 KB ok
28 Correct 92 ms 240980 KB ok
29 Correct 89 ms 240960 KB ok
30 Correct 103 ms 241032 KB ok
31 Correct 101 ms 241036 KB ok
32 Correct 110 ms 241024 KB ok
33 Correct 98 ms 241012 KB ok
34 Correct 94 ms 240976 KB ok
35 Correct 99 ms 241112 KB ok
36 Correct 116 ms 241092 KB ok
37 Correct 99 ms 241084 KB ok
38 Correct 87 ms 240948 KB ok
39 Correct 90 ms 241024 KB ok
40 Correct 110 ms 240996 KB ok
41 Correct 101 ms 240984 KB ok
42 Correct 111 ms 241056 KB ok
43 Correct 95 ms 240964 KB ok
44 Correct 99 ms 241076 KB ok
45 Correct 94 ms 241100 KB ok
46 Correct 99 ms 241120 KB ok
47 Correct 297 ms 262488 KB ok
48 Correct 257 ms 260420 KB ok
49 Correct 390 ms 264284 KB ok
50 Correct 369 ms 264460 KB ok
51 Correct 319 ms 263588 KB ok
52 Correct 165 ms 264488 KB ok
53 Correct 215 ms 254316 KB ok
54 Correct 197 ms 256272 KB ok
55 Correct 3481 ms 259428 KB ok
56 Correct 248 ms 261788 KB ok
57 Correct 137 ms 247128 KB ok
58 Correct 127 ms 245160 KB ok
59 Correct 153 ms 246692 KB ok
60 Correct 166 ms 248512 KB ok
61 Correct 170 ms 252288 KB ok
62 Correct 357 ms 264584 KB ok
63 Correct 396 ms 264520 KB ok
64 Correct 398 ms 264592 KB ok
65 Correct 3867 ms 584200 KB ok
66 Correct 894 ms 386900 KB ok
67 Correct 555 ms 321144 KB ok
68 Execution timed out 4580 ms 616652 KB Time limit exceeded
69 Halted 0 ms 0 KB -