Submission #1209776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209776		PagodePaiva	Soccer Stadium (IOI23_soccer)	C++20	9 / 100	186 ms	31784 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 2010;
int linha_l[N], linha_r[N], coluna_l[N], coluna_r[N];
int ans[N][N][4];

int biggest_stadium(int n, vector<vector<int>> m){
    int tot = 0;
    for(int i = 0;i < n;i++){
        int aux = 0;
        for(int j = 0;j < n;j++){
            if(m[i][j] == 0){
                tot++;
            }
            if(m[i][j] == 0 and aux == 0){
                aux = 1;
            }
            if(m[i][j] == 1 and aux == 1){
                aux = 2;
            }
            if(m[i][j] == 0 and aux == 2){
                return 0;
            }
        }
    }
    for(int j = 0;j < n;j++){
        int aux = 0;
        for(int i = 0;i < n;i++){
            if(m[i][j] == 0 and aux == 0){
                aux = 1;
            }
            if(m[i][j] == 1 and aux == 1){
                aux = 2;
            }
            if(m[i][j] == 0 and aux == 2){
                return 0;
            }
        }
    }
    for(int i = 0;i < n;i++){
        linha_l[i] = n+1, linha_r[i] = -1;
        for(int j = 0;j < n;j++){
            if(m[i][j] == 0){
                linha_l[i] = min(linha_l[i], j);
                linha_r[i] = max(linha_r[i], j);
            }
        }
    }
    for(int j = 0;j < n; j++){
        coluna_l[j] = n+1, coluna_r[j] = -1;
        for(int i = 0;i < n;i++){
            if(m[i][j] == 0){
                coluna_l[j] = min(coluna_l[j], i);
                coluna_r[j] = max(coluna_r[j], i);
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            ans[i][j][0] = max({ans[i][j][0], (i > 0 ? ans[i-1][j][0] : 0), (j > 0 ? ans[i][j-1][0] : 0), (m[i][j] == 0 ? 1 : 0)});
        }
    }   
    for(int i = 0;i < n;i++){
        for(int j = n-1;j >= 0;j--){
            ans[i][j][1] = max({ans[i][j][1], (i > 0 ? ans[i-1][j][1] : 0), (j < n-1 ? ans[i][j+1][1] : 0), (m[i][j] == 0 ? 1 : 0)});
        }
    } 
    for(int i = n-1;i >= 0;i--){
        for(int j = n-1;j >= 0;j--){
            ans[i][j][2] = max({ans[i][j][2], (i < n-1 ? ans[i+1][j][2] : 0), (j < n-1 ? ans[i][j+1][2] : 0), (m[i][j] == 0 ? 1 : 0)});
        }
    } 
    for(int i = n-1;i >= 0;i--){
        for(int j = 0;j < n;j++){
            ans[i][j][3] = max({ans[i][j][3], (i < n-1 ? ans[i+1][j][3] : 0), (j >= 0 ? ans[i][j-1][3] : 0), (m[i][j] == 0 ? 1 : 0)});
        }
    } 
    for(int k = 0;k < 4;k++){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(m[i][j] == 1)
                continue;
            if(linha_l[i] > 0 and coluna_l[j] > 0){
                if(ans[linha_l[i]-1][coluna_l[j]-1][0]){
                    return 0;
                }
            }
            if(linha_l[i] > 0 and coluna_r[j] < n-1){
                if(ans[linha_l[i]-1][coluna_r[j]+1][1]){
                    return 0;
                }
            }
            if(linha_r[i] < n-1 and coluna_r[j] < n-1){
                if(ans[linha_r[i]+1][coluna_r[j]+1][2]){
                    return 0;
                }
            }
            if(linha_r[i] < n-1 and coluna_l[j] > 0){
                if(ans[linha_r[i]+1][coluna_l[j]-1][3]){
                    return 0;
                }
            }
        }
    }
    return tot;
}

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