Submission #1070726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070726		zsombor	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	663 ms	1003344 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

int n, ans = 0;
vector<vector<bool> > t(3e3, vector<bool>(3e3, false));
vector<vector<vector<int> > > dp(3e3, vector<vector<int> >(3e3, vector<int>(4, -1e9)));

void u(int i, int l, int r, int x, int y, int val) {
    int j = 2 * n * l + r;
    int k = 2 * x + y;
    dp[i][j][k] = val;
}

int q(int i, int l, int r, int x, int y) {
    int j = 2 * n * l + r;
    int k = 2 * x + y;
    return dp[i][j][k];
}

void get_dp(int i, int l, int r, int x, int y) {
    for (int j = l; j <= r; j++) if (t[i][j]) return;
    int mx = 0, L1 = 1, Ln = n, R1 = 1, Rn = n;
    (x ? Ln = l : L1 = l);
    (y ? R1 = r : Rn = r);
    for (int L = L1; L <= Ln; L++) {
        for (int R = R1; R <= Rn; R++) {
            if (R < L || R < l || r < L) continue;
            mx = max(mx, q(i - 1, L, R, x, y));
        }
    }
    for (int X = 0; X <= x; X++) {
        for (int Y = 0; Y <= y; Y++) {
            mx = max(mx, q(i - 1, l, r, X, Y));
        }
    }
    mx += (r - l) + 1;
    u(i, l, r, x, y, mx);
    ans = max(ans, mx);
}

int biggest_stadium(int N, std::vector<std::vector<int> > F) {
    n = N;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            t[i][j] = F[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) {
                for (int x = 0; x < 2; x++) {
                    for (int y = 0; y < 2; y++) {
                        get_dp(i, l, r, x, y);
                    }
                }
            }
        }
    }
    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