Submission #1214125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214125		trimkus	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	4 ms	4164 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<int>> F;
int N;
int dp[31][31][31][31];
vector<vector<array<int, 2>>> spans(31);
int get_cnt(int i, int lj, int rj) {
    int res = 0;
    for (int j = lj; j <= rj; ++j) {
        res += (F[i][j] == 0);
    }
    return res;
}
bool intersects(array<int, 2> A, array<int, 2> B) {
    return (A[0] <= B[0] && B[0] <= A[1]) || (B[0] <= A[0] && A[0] <= B[1]);
}
int solve(int li, int ri, int leftbound, int rightbound, int nowi) {
    // cerr << li << " " << ri << " " << leftbound << " " << rightbound << " " << nowi << "\n";
    if (li < 0) return 0;
    if (ri >= N) return 0;
    // if (dp[li][ri][leftbound][rightbound] != -1) return dp[li][ri][leftbound][rightbound];
    int cnt = get_cnt(nowi, leftbound, rightbound);
    int add = 0;
    if (li - 1 >= 0 && li == nowi) {
        for (auto B : spans[li - 1]) {
            if (intersects({leftbound, rightbound}, B)) {
                add = max(add, solve(li - 1, ri, max(leftbound, B[0]), min(rightbound, B[1]), li - 1));
            }
        }
    }
    if (ri + 1 < N && ri == nowi) {
        for (auto B : spans[ri + 1]) {
            if (intersects({leftbound, rightbound}, B)) {
                add = max(add, solve(li, ri + 1, max(leftbound, B[0]), min(rightbound, B[1]), ri + 1));
            }
        }
    }
    return dp[li][ri][leftbound][rightbound] = max(dp[li][ri][leftbound][rightbound], add + cnt);
}

int biggest_stadium(int _N, std::vector<std::vector<int>> _F)
{
    N = _N;
    F = _F;
    int res = 0;
    cerr << "Here!\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                for (int z = 0; z < N; ++z) {
                    dp[i][j][k][z] = -1;
                }
            }
        }
    }
    cerr << "Starting to get spans:\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N;) {
            if (F[i][j] == 1) {
                j++;
                continue;
            }
            int k = j;
            while (k < N && F[i][k] == 0) k += 1;
            spans[i].push_back({j, k - 1});
            j = k;
        }
    }
    cerr << "Starting to recurse:\n";
    for (int i = 0; i < N; ++i) {
        for (auto& [j, k] : spans[i]) {
            solve(i, i, j, k, i);
            // cerr << "Done with this span\n";
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                for (int z = 0; z < N; ++z) {
                    res = max(res, dp[i][j][k][z]);
                }
            }
        }
    }
    return res;
}

• 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