oj.uz

Submission #839768

# Submission time Handle Problem Language Result Execution time Memory
839768 2023-08-30T15:50:41 Z model_code Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 264548 KB 
// correct/n4_hist.cpp

#include "soccer.h"
#include <iostream>
#include <array>
#include <map>
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 calc(int ind)
    {
        if (dp[ind] != -1)
            return dp[ind];
        int area = (rects[ind][2] - rects[ind][0] + 1) * (rects[ind][3] - rects[ind][1] + 1);
        int ans = area;
        for (int i = 0; i < (int)rects.size(); i++)
        {
            if (ind == i)
                continue;
            if (rects[i][0] <= rects[ind][0] && rects[ind][2] <= rects[i][2] &&
                rects[ind][1] <= rects[i][1] && rects[i][3] <= rects[ind][3])
            {
                ans = std::max(ans, area + calc(i) - (rects[ind][2] - rects[ind][0] + 1) * (rects[i][3] - rects[i][1] + 1));
            }
        }

        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 82 ms 240976 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 240944 KB ok
2 Correct 79 ms 241024 KB ok
3 Correct 80 ms 240992 KB ok
4 Correct 81 ms 240948 KB ok
5 Correct 86 ms 241040 KB ok
6 Correct 88 ms 240972 KB ok
7 Correct 435 ms 241984 KB ok
8 Execution timed out 4544 ms 264548 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 240944 KB ok
2 Correct 79 ms 241024 KB ok
3 Correct 86 ms 241008 KB ok
4 Correct 95 ms 240976 KB ok
5 Correct 74 ms 240972 KB ok
6 Correct 83 ms 241120 KB ok
7 Correct 105 ms 240972 KB ok
8 Correct 80 ms 240924 KB ok
9 Correct 83 ms 241008 KB ok
10 Correct 76 ms 240996 KB ok
11 Correct 75 ms 240980 KB ok
12 Correct 92 ms 241156 KB ok
13 Correct 91 ms 241028 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 240976 KB ok
2 Correct 80 ms 240944 KB ok
3 Correct 79 ms 241024 KB ok
4 Correct 86 ms 241008 KB ok
5 Correct 95 ms 240976 KB ok
6 Correct 74 ms 240972 KB ok
7 Correct 83 ms 241120 KB ok
8 Correct 105 ms 240972 KB ok
9 Correct 80 ms 240924 KB ok
10 Correct 83 ms 241008 KB ok
11 Correct 76 ms 240996 KB ok
12 Correct 75 ms 240980 KB ok
13 Correct 92 ms 241156 KB ok
14 Correct 91 ms 241028 KB ok
15 Correct 91 ms 240952 KB ok
16 Correct 91 ms 240980 KB ok
17 Correct 87 ms 240976 KB ok
18 Correct 85 ms 240924 KB ok
19 Correct 80 ms 240976 KB ok
20 Correct 115 ms 241032 KB ok
21 Correct 105 ms 240952 KB ok
22 Correct 104 ms 241008 KB ok
23 Correct 111 ms 241020 KB ok
24 Correct 126 ms 240952 KB ok
25 Correct 99 ms 240992 KB ok
26 Correct 88 ms 241028 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 240976 KB ok
2 Correct 80 ms 240944 KB ok
3 Correct 79 ms 241024 KB ok
4 Correct 80 ms 240992 KB ok
5 Correct 81 ms 240948 KB ok
6 Correct 86 ms 241008 KB ok
7 Correct 95 ms 240976 KB ok
8 Correct 74 ms 240972 KB ok
9 Correct 83 ms 241120 KB ok
10 Correct 105 ms 240972 KB ok
11 Correct 80 ms 240924 KB ok
12 Correct 83 ms 241008 KB ok
13 Correct 76 ms 240996 KB ok
14 Correct 75 ms 240980 KB ok
15 Correct 92 ms 241156 KB ok
16 Correct 91 ms 241028 KB ok
17 Correct 91 ms 240952 KB ok
18 Correct 91 ms 240980 KB ok
19 Correct 87 ms 240976 KB ok
20 Correct 85 ms 240924 KB ok
21 Correct 80 ms 240976 KB ok
22 Correct 115 ms 241032 KB ok
23 Correct 105 ms 240952 KB ok
24 Correct 104 ms 241008 KB ok
25 Correct 111 ms 241020 KB ok
26 Correct 126 ms 240952 KB ok
27 Correct 99 ms 240992 KB ok
28 Correct 88 ms 241028 KB ok
29 Correct 119 ms 240956 KB ok
30 Correct 120 ms 241096 KB ok
31 Correct 118 ms 241072 KB ok
32 Correct 120 ms 241092 KB ok
33 Correct 95 ms 240972 KB ok
34 Correct 84 ms 241016 KB ok
35 Correct 94 ms 241076 KB ok
36 Correct 94 ms 240956 KB ok
37 Correct 98 ms 241008 KB ok
38 Correct 90 ms 241036 KB ok
39 Correct 87 ms 240964 KB ok
40 Correct 92 ms 241080 KB ok
41 Correct 102 ms 241060 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 240976 KB ok
2 Correct 80 ms 240944 KB ok
3 Correct 79 ms 241024 KB ok
4 Correct 80 ms 240992 KB ok
5 Correct 81 ms 240948 KB ok
6 Correct 86 ms 241008 KB ok
7 Correct 95 ms 240976 KB ok
8 Correct 74 ms 240972 KB ok
9 Correct 83 ms 241120 KB ok
10 Correct 105 ms 240972 KB ok
11 Correct 80 ms 240924 KB ok
12 Correct 83 ms 241008 KB ok
13 Correct 76 ms 240996 KB ok
14 Correct 75 ms 240980 KB ok
15 Correct 92 ms 241156 KB ok
16 Correct 91 ms 241028 KB ok
17 Correct 91 ms 240952 KB ok
18 Correct 91 ms 240980 KB ok
19 Correct 87 ms 240976 KB ok
20 Correct 85 ms 240924 KB ok
21 Correct 80 ms 240976 KB ok
22 Correct 115 ms 241032 KB ok
23 Correct 105 ms 240952 KB ok
24 Correct 104 ms 241008 KB ok
25 Correct 111 ms 241020 KB ok
26 Correct 126 ms 240952 KB ok
27 Correct 99 ms 240992 KB ok
28 Correct 88 ms 241028 KB ok
29 Correct 119 ms 240956 KB ok
30 Correct 120 ms 241096 KB ok
31 Correct 118 ms 241072 KB ok
32 Correct 120 ms 241092 KB ok
33 Correct 95 ms 240972 KB ok
34 Correct 84 ms 241016 KB ok
35 Correct 94 ms 241076 KB ok
36 Correct 94 ms 240956 KB ok
37 Correct 98 ms 241008 KB ok
38 Correct 90 ms 241036 KB ok
39 Correct 87 ms 240964 KB ok
40 Correct 92 ms 241080 KB ok
41 Correct 102 ms 241060 KB ok
42 Execution timed out 4519 ms 262936 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 240976 KB ok
2 Correct 80 ms 240944 KB ok
3 Correct 79 ms 241024 KB ok
4 Correct 80 ms 240992 KB ok
5 Correct 81 ms 240948 KB ok
6 Correct 86 ms 241040 KB ok
7 Correct 88 ms 240972 KB ok
8 Correct 435 ms 241984 KB ok
9 Execution timed out 4544 ms 264548 KB Time limit exceeded
10 Halted 0 ms 0 KB -