제출 #1190502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190502		anmattroi	Soccer Stadium (IOI23_soccer)	C++17	1.50 / 100	247 ms	126064 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define maxn 2005
using namespace std;

int n, f[maxn][maxn], s[maxn][maxn];
int xL[maxn][maxn], xR[maxn][maxn], xU[maxn][maxn], xD[maxn][maxn];

int biggest_stadium(int N, vector<vector<int>> F) {
    n = N;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = F[i-1][j-1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + 1 - f[i][j];

    function<int(int, int, int, int)> getRect = [&](int u, int v, int x, int y) {
        return s[x][y] - s[u-1][y] - s[x][v-1] + s[u-1][v-1];
    };

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
    if (f[i][j]) {
        xU[i][j] = getRect(1, j, i, j);
        xD[i][j] = getRect(i, j, n, j);
        xL[i][j] = getRect(i, 1, i, j);
        xR[i][j] = getRect(i, j, i, n);
    }
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        xU[i][j] += xU[i-1][j] + xU[i][j-1] - xU[i-1][j-1];
        xD[i][j] += xD[i-1][j] + xD[i][j-1] - xD[i-1][j-1];
        xL[i][j] += xL[i-1][j] + xL[i][j-1] - xL[i-1][j-1];
        xR[i][j] += xR[i-1][j] + xR[i][j-1] - xR[i-1][j-1];
    }
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    if (f[i][j]) {
        if (getRect(1, j, i, j) && (xD[n][n] - xD[n][0] - xD[i-1][n] + xD[i-1][0])) return 0;
        if (getRect(i, j, n, j) && xU[i][n]) return 0;
        if (getRect(i, 1, i, j) && (xR[n][n] - xR[0][n] - xR[n][j-1] + xR[0][j-1])) return 0;
        if (getRect(i, j, i, n) && xL[n][j]) return 0;
    }
    return s[n][n];
}

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