oj.uz

Submission #1078441

# Submission time Handle Problem Language Result Execution time Memory
1078441 2024-08-27T17:26:48 Z PanosPask Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1717 ms 2097152 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

int N;
vector<vector<int>> grid;
vector<vector<int>> pref;

vector<vector<vector<int>>> above;
vector<vector<vector<int>>> below;

// Returns true if the cells (i, l) to (i, r) are all free
bool whole(int i, int l, int r)
{
    int res = pref[i][r];
    if (l) {
        res -= pref[i][l - 1];
    }

    return res == 0;
}

/* dp[i][l][r]:
 * Maximum size of a regular field that covers rows [0..i] and has the largest interval [l..r] at row i
 */ 
void calculate(vector<vector<vector<int>>>& dp)
{
    dp.assign(N, vector<vector<int>>(N, vector<int>(N, 0)));

    for (int i = 0; i < N; i++) {        
        for (int len = 1; len <= N; len++) {
            for (int l = 0; l + len <= N; l++) {
                int r = l + len - 1;

                if (len != 1) {
                    dp[i][l][r] = max(dp[i][l + 1][r], dp[i][l][r - 1]);
                }

                if (whole(i, l, r)) {
                    int v = len;
                    if (i) {
                        v += dp[i - 1][l][r];
                    }

                    dp[i][l][r] = max(dp[i][l][r], v);
                }
            }
        }
    }
}

int biggest_stadium(int n, std::vector<std::vector<int>> F)
{
    N = n;
    grid.resize(N, vector<int>(N));
    pref.resize(N, vector<int>(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            grid[i][j] = F[i][j];
            pref[i][j] = F[i][j];
            if (j) {
                pref[i][j] += pref[i][j - 1];
            }
        }
    }

    calculate(above);

    reverse(grid.begin(), grid.end());
    reverse(pref.begin(), pref.end());    
    calculate(below);
    reverse(grid.begin(), grid.end());
    reverse(pref.begin(), pref.end());
    reverse(below.begin(), below.end());

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int len = 1; len <= N; len++) {
            for (int l = 0; l + len <= N; l++) {
                int r = l + len - 1;
                if (whole(i, l, r)) {
                    int v = len;
                    if (i) {
                        v += above[i - 1][l][r];
                    }
                    if (i < N - 1) {
                        v += below[i + 1][l][r];
                    }

                    ans = max(ans, v);
                }
            }
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 380 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 12 ms 9196 KB ok
8 Correct 1717 ms 1004116 KB ok
9 Runtime error 1134 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 356 KB ok
4 Correct 0 ms 344 KB ok
5 Incorrect 0 ms 356 KB wrong
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

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

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 380 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 12 ms 9196 KB ok
9 Correct 1717 ms 1004116 KB ok
10 Runtime error 1134 ms 2097152 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -