oj.uz

Submission #1072068

# Submission time Handle Problem Language Result Execution time Memory
1072068 2024-08-23T13:53:05 Z Mihailo Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 198740 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>1; 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>1; 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));
    }
    return sol;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 604 KB ok
4 Correct 0 ms 448 KB ok
5 Correct 1 ms 2492 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 3 ms 2508 KB ok
8 Correct 309 ms 18872 KB ok
9 Execution timed out 4520 ms 198740 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 1 ms 2396 KB partial
4 Partially correct 0 ms 348 KB partial
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Incorrect 1 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 1 ms 2396 KB partial
5 Partially correct 0 ms 348 KB partial
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Incorrect 1 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 448 KB ok
6 Partially correct 1 ms 2396 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Incorrect 1 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 448 KB ok
6 Partially correct 1 ms 2396 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Incorrect 1 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 448 KB ok
6 Correct 1 ms 2492 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 3 ms 2508 KB ok
9 Correct 309 ms 18872 KB ok
10 Execution timed out 4520 ms 198740 KB Time limit exceeded
11 Halted 0 ms 0 KB -