Submission #839768

#	Time	Username	Problem	Language	Result	Execution time	Memory
839768		model_code	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4544 ms	264548 KiB

soccer

// 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
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30