oj.uz

Submission #1072116

# Submission time Handle Problem Language Result Execution time Memory
1072116 2024-08-23T14:27:47 Z Mihailo Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 6492 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4549 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4558 ms 6492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4558 ms 6492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4549 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4549 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4549 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4549 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -