Submission #839759

#	Time	Username	Problem	Language	Result	Execution time	Memory
839759		model_code	Soccer Stadium (IOI23_soccer)	C++17	70 / 100	4580 ms	616912 KiB

soccer

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