Submission #1213904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213904		trimkus	Soccer Stadium (IOI23_soccer)	C++20	25 / 100	556 ms	486580 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    auto can = [&](int i, int j) -> bool {
        return max(i, j) < N && min(i, j) >= 0 && F[i][j] == 0;
    };
    vector<vector<bool>> vis(N, vector<bool>(N));
    int cnt = 0, res = 0;
    auto dfs = [&](auto& dfs, int i, int j) -> void {
        vis[i][j] = 1;
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (max(ni, nj) >= N || min(ni, nj) < 0 || vis[ni][nj] || F[ni][nj] == 1) continue;
            dfs(dfs, ni, nj);
        }
    };
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!vis[i][j] && F[i][j] == 0) {
                dfs(dfs, i, j);
                cnt += 1;
            }
            res += (F[i][j] == 0);
        }
    }
    if (cnt > 1) return 0;
    vector<vector<int>> dp(N, vector<int>(N));
    vector<vector<int>> left(N, vector<int>(N, -1)), right(N, vector<int>(N, -1));
    vector<vector<int>> up(N, vector<int>(N, -1)), down(N, vector<int>(N, -1));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i][j] += F[i][j];
            if (i) {
                dp[i][j] += dp[i - 1][j];
            }
            if (j) {
                dp[i][j] += dp[i][j - 1];
            }
            if (i && j) {
                dp[i][j] -= dp[i - 1][j - 1];
            }
            if (F[i][j] == 0) {
                left[i][j] = j;
                up[i][j] = i;
            }
            if (j > 0) {
                if (left[i][j - 1] != -1) left[i][j] = left[i][j - 1];
            }
            if (i > 0) {
                if (up[i - 1][j] != -1) up[i][j] = up[i - 1][j];
            }
        }
    }
    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            if (F[i][j] == 0) {
                right[i][j] = j;
                down[i][j] = i;
            }
            if (j + 1 < N) {
                if (right[i][j + 1] != -1) right[i][j] = right[i][j + 1];
            }
            if (i + 1 < N) {
                if (down[i + 1][j] != -1) down[i][j] = down[i + 1][j];
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (F[i][j] == 1) {
                if (left[i][j] != -1 && right[i][j] != -1) return 0;
                if (up[i][j] != -1 && down[i][j] != -1) return 0;
            }
        }
    }
    vector<array<int, 4>> sz;
    for (int i = 0; i < N; ++i) {
        int now = 0;
        for (int j = 0; j < N;) {
            if (F[i][j] == 1) {
                j++;
                continue;
            }
            while (j < N && F[i][j] == 0) {
                now += 1;
                j++;
            }
            sz.push_back({now, j - now, j - 1, 0});
        }
    }
    vector<array<int, 2>> intervals;
    int st = -1, en = -1;
    {
        for (int i = 0; i < N && st == -1; ++i) {
            for (int j = 0; j < N && st == -1; ++j) {
                if (F[i][j] == 0) st = i;
            }
        }
        for (int i = N - 1; i >= 0 && en == -1; --i) {
            for (int j = 0; j < N && en == -1; ++j) {
                if (F[i][j] == 0) en = i;
            }
        }
    }
    auto contains = [&](array<int, 2> A, array<int, 2> B) -> bool {
        return A[0] <= B[0] && B[1] <= A[1];
    };
    for (int i = st; i <= en; ++i) {
        array<int, 2> now = {-1, -1};
        for (int j = 0; j < N; ++j) {
            if (F[i][j] == 0) {
                now[0] = j;
                break;
            }
        }
        for (int j = N - 1; j >= now[0]; --j) {
            if (F[i][j] == 0) {
                now[1] = j;
                break;
            }
        }
        for (auto& v : intervals) {
            if (!contains(v, now) && !contains(now, v)) {
                return 0;
            }
        }
        intervals.push_back(now);
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 6
• Subtask 2: 2 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 4 / 16
• Subtask 6: 7.5 / 30