Submission #1072116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072116		Mihailo	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	4558 ms	6492 KiB

soccer

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;

pair<int, int> gore[3000][3000], dole[3000][3000], levo[3000][3000], deso[3000][3000];
int n;

int stadsize(int x, int y) {
    if(gore[x][y]==mp(x, y)) return 0;
    int maxgore=gore[x][y].yy;
    int mindole=dole[x][y].yy;
    int rez=0;
    for(int i=0; true; i++) {
        if(x+i>n||gore[x+i][y]==mp(x+i, y)) break;
        maxgore=max(maxgore, gore[x+i][y].yy);
        mindole=min(mindole, dole[x+i][y].yy);
        rez+=-maxgore+mindole-1;
    }
    maxgore=gore[x][y].yy;
    mindole=dole[x][y].yy;
    for(int i=-1; true; i--) {
        if(x+i<1||gore[x+i][y]==mp(x+i, y)) break;
        maxgore=max(maxgore, gore[x+i][y].yy);
        mindole=min(mindole, dole[x+i][y].yy);
        rez+=-maxgore+mindole-1;
    }
    return rez;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    {
        for(int i=1; i<=N; i++) {
            if(F[i-1][0]) gore[i][1]=mp(i, 1);
            else gore[i][1]=mp(i, 0);
        }
        for(int i=2; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(F[j-1][i-1]) gore[j][i]=mp(j, i);
                else gore[j][i]=gore[j][i-1];
            }
        }
        for(int i=1; i<=N; i++) {
            if(F[i-1][N-1]) dole[i][N]=mp(i, N);
            else dole[i][N]=mp(i, N+1);
        }
        for(int i=N-1; i>0; i--) {
            for(int j=1; j<=N; j++) {
                if(F[j-1][i-1]) dole[j][i]=mp(j, i);
                else dole[j][i]=dole[j][i+1];
            }
        }
        for(int i=1; i<=N; i++) {
            if(F[0][i-1]) levo[1][i]=mp(1, i);
            else levo[1][i]=mp(0, i);
        }
        for(int i=2; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(F[i-1][j-1]) levo[i][j]=mp(i, j);
                else levo[i][j]=levo[i-1][j];
            }
        }
        for(int i=1; i<=N; i++) {
            if(F[N-1][i-1]) deso[N][i]=mp(N, i);
            else deso[N][i]=mp(N+1, i);
        }
        for(int i=N-1; i>0; i--) {
            for(int j=1; j<=N; j++) {
                if(F[i-1][j-1]) deso[i][j]=mp(i, j);
                else deso[i][j]=deso[i+1][j];
            }
        }
    }
    n=N;
    int sol=0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) sol=max(sol, stadsize(i, j));
    }
    int prazna=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) if(!F[i][j]) prazna++;
    }
    if(sol<=prazna) while(true);
    return sol;
}

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