Submission #963751

#	Time	Username	Problem	Language	Result	Execution time	Memory
963751		tutis	Soccer Stadium (IOI23_soccer)	C++17	70 / 100	4553 ms	119416 KiB

soccer

//#include "soccer.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int biggest_stadium(int N, std::vector<std::vector<int>> C) {
    vector<vector<int>> S(N);
    auto fS = [&](int x, int y) {
        if (x < 0 || y < 0) {
            return 0;
        }
        if (x >= N) {
            x = N - 1;
        }
        if (y >= N) {
            y = N - 1;
        }
        return S[x][y];
    };
    auto sm = [&](int x1, int x2, int y1, int y2) -> int {
        return fS(x2, y2) - fS(x1 - 1, y2) - fS(x2, y1 - 1) + fS(x1 - 1, y1 - 1);
    };
    for (int i = 0; i < N; i++) {
        S[i] = vector<int>(N);
        for (int j = 0; j < N; j++) {
            S[i][j] = C[i][j];
            S[i][j] += fS(i - 1, j) + fS(i, j - 1) - fS(i - 1, j - 1);
        }
    }
    int best = 0;
    vector<pair<pair<int, int>, pair<int, int>>> V;
    function<void(int, int, int, int)> dfs = [&](int x1, int x2, int y1, int y2) -> void {
        if (y1 > y2) {
            return;
        }
        if (x2 != N - 1 && sm(x2 + 1, x2 + 1, y1, y2) == 0) {
            return;
        }
        if (x1 == 0) {
            V.push_back({{x1, x2},
                         {y1, y2}});
            return;
        }
        if (sm(x1 - 1, x1 - 1, y1, y2) != 0) {
            V.push_back({{x1, x2},
                         {y1, y2}});
        }
        int lst = y1 - 1;
        for (int y = y1; y <= y2 + 1; y++) {
            if (y == y2 + 1 || C[x1 - 1][y] == 1) {
                dfs(x1 - 1, x2, lst + 1, y - 1);
                lst = y;
            }
        }
    };
    for (int x = 0; x < N; x++) {
        int lst = -1;
        for (int y = 0; y <= N; y++) {
            if (y == N || C[x][y] == 1) {
                if (lst + 1 > y - 1) {
                    lst = y;
                    continue;
                }
                if (x != N - 1 && sm(x + 1, x + 1, lst + 1, y - 1) == 0) {
                    lst = y;
                    continue;
                }
                dfs(x, x, lst + 1, y - 1);
                lst = y;
            }
        }
    }
    sort(V.begin(), V.end(),
         [&](pair<pair<int, int>, pair<int, int>> a, pair<pair<int, int>, pair<int, int>> b) {
             return a.second.second - a.second.first > b.second.second - b.second.first;
         });
    map<pair<pair<int, int>, pair<int, int>>, int> M;
    auto check = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        if (y0 > y1) {
            return;
        }
        while (x0 != 0 && sm(x0 - 1, x0 - 1, y0, y1) == 0) {
            x0--;
            area += (y1 - y0 + 1);
        }
        while (x1 != N - 1 && sm(x1 + 1, x1 + 1, y0, y1) == 0) {
            x1++;
            area += (y1 - y0 + 1);
        }
        M[{{x0, x1},
           {y0, y1}}] = max(M[{{x0, x1},
                               {y0, y1}}],
                            area);
    };
    auto expL = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        if (y0 > y1) {
            return;
        }
        int lst = y0 - 1;
        for (int y = y0; y <= y1 + 1; y++) {
            if (y == y1 + 1 || C[x0 - 1][y] == 1) {
                check({{x0 - 1,  x1},
                       {lst + 1, y - 1}}, area + (y - 1) - (lst + 1) + 1);
                lst = y;
            }
        }
    };
    auto expR = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        if (y0 > y1) {
            return;
        }
        int lst = y0 - 1;
        for (int y = y0; y <= y1 + 1; y++) {
            if (y == y1 + 1 || C[x1 + 1][y] == 1) {
                check({{x0,      x1 + 1},
                       {lst + 1, y - 1}}, area + (y - 1) - (lst + 1) + 1);
                lst = y;
            }
        }
    };
    for (auto i: V) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        int dp = (x1 - x0 + 1) * (y1 - y0 + 1);
        if (M.count(i)) {
            dp = M[i];
        } else {
            M[i] = dp;
        }
        int ans = dp;
        best = max(best, ans);
        if (x0 != 0) {
            expL(i, ans);
        }
        if (x1 != N - 1) {
            expR(i, ans);
        }
    }

    return best;
}

• 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