oj.uz

Submission #1066520

# Submission time Handle Problem Language Result Execution time Memory
1066520 2024-08-20T00:12:11 Z aaaaaarroz Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

int biggest_stadium(int N, vector<vector<int>> F) {
    map<tuple<int, int, int>, bool> libre;

    // Construir mapa de celdas libres
    for (int fila = 0; fila < N; fila++) {
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                if (i == j) {
                    libre[{fila, i, j}] = !F[fila][j];
                } else {
                    libre[{fila, i, j}] = (!F[fila][j]) && libre[{fila, i, j - 1}];
                }
            }
        }
    }

    int best = 0;

    // Iterar sobre cada fila y columna
    for (int fila = 0; fila < N; fila++) {
        for (int columna = 0; columna < N; columna++) {
            for (int i = 0; i <= columna; i++) {
                for (int j = columna; j < N; j++) {
                    if (libre[{fila, i, j}]) {
                        vector<pair<int, int>> almacen;
                        almacen.push_back({i, j});
                        int suma = 0;

                        // Expandir hacia arriba
                        int fil = fila - 1;
                        while (fil >= 0 && F[fil][columna] != 1) {
                            int l = columna, r = columna;
                            while (l >= almacen.back().first && r <= almacen.back().second) {
                                if (libre[{fil, l - 1, r}] && (l - 1) >= almacen.back().first) {
                                    l--;
                                } else if (libre[{fil, l, r + 1}] && (r + 1) <= almacen.back().second) {
                                    r++;
                                } else {
                                    break;
                                }
                            }
                            almacen.push_back({l, r});
                            fil--;
                        }

                        // Expandir hacia abajo
                        fil = fila + 1;
                        int fila_extra = 1;
                        int alm_ant = almacen.size() - 1;
                        while (fil < N && F[fil][columna] != 1) {
                            int l = columna, r = columna;
                            if (fila_extra < alm_ant) {
                                l = almacen[fila_extra].first;
                                r = almacen[fila_extra].second;
                            }
                            while (l >= almacen.back().first && r <= almacen.back().second) {
                                if (libre[{fil, l - 1, r}] && (l - 1) >= almacen.back().first) {
                                    l--;
                                } else if (libre[{fil, l, r + 1}] && (r + 1) <= almacen.back().second) {
                                    r++;
                                } else {
                                    break;
                                }
                            }
                            almacen.push_back({l, r});
                            fil++;
                            fila_extra++;
                        }

                        // Calcular suma de todas las expansiones
                        for (auto [x, y] : almacen) {
                            suma += (y - x + 1);
                        }

                        suma -= (j - i + 1);
                        best = max(suma, best);
                    }
                }
            }
        }
    }

    return best;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB wrong
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB wrong
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Incorrect 1 ms 348 KB wrong
3 Halted 0 ms 0 KB -