Submission #1078441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078441		PanosPask	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	1717 ms	2097152 KiB

soccer

#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
• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30