Submission #1078564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078564		myst6	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	297 ms	55544 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

bool dp[4][2005][2005];

int biggest_stadium(int N, vector<vector<int>> F) {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            bool tree = F[i][j] == 1;
            bool to = i == 0 || dp[0][i-1][j];
            bool le = j == 0 || dp[0][i][j-1];
            dp[0][i][j] = tree && to && le;
        }
    }
    for (int i=0; i<N; i++) {
        for (int j=N-1; j>=0; j--) {
            bool tree = F[i][j] == 1;
            bool to = i == 0 || dp[1][i-1][j];
            bool ri = j == N-1 || dp[1][i][j+1];
            dp[1][i][j] = tree && to && ri;
        }
    }
    for (int i=N-1; i>=0; i--) {
        for (int j=0; j<N; j++) {
            bool tree = F[i][j] == 1;
            bool bo = i == N-1 || dp[2][i+1][j];
            bool le = j == 0 || dp[2][i][j-1];
            dp[2][i][j] = tree && bo && le;
        }
    }
    for (int i=N-1; i>=0; i--) {
        for (int j=N-1; j>=0; j--) {
            bool tree = F[i][j] == 1;
            bool bo = i == N-1 || dp[3][i+1][j];
            bool ri = j == N-1 || dp[3][i][j+1];
            dp[3][i][j] = tree && bo && ri;
        }
    }

    bool entire = true;
    int sz = 0;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            bool tree = F[i][j] == 1;
            if (tree && !dp[0][i][j] && !dp[1][i][j] && !dp[2][i][j] && !dp[3][i][j]) {
                entire = false;
                // cout << i << "," << j << "\n";
                break;
            }
            sz += 1 - tree;
        }
    }

    // check row intervals work
    int i1 = 0, i2 = N-1;
    while (i1 < i2) {
        int tl = -1, tr = N;
        for (int j=0; j<N; j++) {
            if (dp[0][i1][j]) tl = j;
            else break;
        }
        for (int j=N-1; j>=0; j--) {
            if (dp[1][i1][j]) tr = j;
            else break;
        }

        int bl = -1, br = N;
        for (int j=0; j<N; j++) {
            if (dp[2][i2][j]) bl = j;
            else break;
        }
        for (int j=N-1; j>=0; j--) {
            if (dp[3][i2][j]) br = j;
            else break;
        }

        int l = max(bl, tl);
        int r = min(br, tr);
        
        if (l == tl && r == tr) i1++;
        else if (l == bl && r == br) i2--;
        else { entire = false; break; }
    }

    // check column intervals work
    int j1 = 0, j2 = N-1;
    while (j1 < j2) {
        int tl = -1, bl = N;
        for (int i=0; i<N; i++) {
            if (dp[0][i][j1]) tl = i;
            else break;
        }
        for (int i=N-1; i>=0; i--) {
            if (dp[2][i][j1]) bl = i;
            else break;
        }

        int tr = -1, br = N;
        for (int i=0; i<N; i++) {
            if (dp[1][i][j2]) tr = i;
            else break;
        }
        for (int i=N-1; i>=0; i--) {
            if (dp[3][i][j2]) br = i;
            else break;
        }

        int t = max(tl, tr);
        int b = min(bl, br);
            
        if (t == tr && b == br) j1++;
        else if (t == tl && b == bl) j2--;
        else { entire = false; break; }
    }

    if (entire) {
        return sz;
    } else {
        return 0;
    }
}

• 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