Submission #839760

#	Time	Username	Problem	Language	Result	Execution time	Memory
839760		model_code	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4609 ms	495484 KiB

soccer

// correct/sol_db_N6.cpp

#include "soccer.h"
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cassert>
#include <string.h>
#define xx first
#define yy second

using namespace std;
typedef pair <int, int> pii;
const int maxN = 501;
int N, dp[maxN][maxN][maxN];

vector <vector <int>> pre;

int query(int li, int lj, int ri, int rj) {
    return pre[ri][rj] - (li? pre[li - 1][rj] : 0) - (lj? pre[ri][lj - 1] : 0) + (li && lj? pre[li - 1][lj - 1] : 0);
}

pii calc_range(int i, int l, int r) {
    int li = i - 1, ri = i;
    while (li >= 0 && query(li, l, i - 1, r) == 0) li--;
    while (ri < N && query(i, l, ri, r) == 0) ri++;
    return make_pair(li, ri);
}

int calc(int i, int l, int r) {
    if (dp[i][l][r] != -1) {
        return dp[i][l][r];
    }
    pii range = calc_range(i, l, r);
    int li = range.xx;
    int ri = range.yy;
    int res = 0;

    for (int L = l; L <= r; ++L) {
        for (int R = L; R <= r; ++R) {
            if (L == l && R == r) {
                continue;
            }
            int Li = li;
            int Ri = ri;
            while (Li >= 0 && query(Li, L, i - 1, R) == 0) Li--;
            while (Ri < N && query(i, L, Ri, R) == 0) Ri++;
            res = max(res, calc(i, L, R) + (R - L + 1) * (li - Li + Ri - ri));
        }
    }
    return dp[i][l][r] = res;
}

int biggest_stadium(int n, vector <vector <int>> C) {
    N = n, pre = C;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            pre[i][j] += (j? pre[i][j - 1]: 0);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            pre[i][j] += (i? pre[i - 1][j]: 0);
        }
    }
    memset(dp, -1, sizeof dp);
    int res = 0;
    for (int i = 0; i < N; ++i) {
        pii range = calc_range(i, 0, N - 1);
        res = max(res, calc(i, 0, N - 1) + N * (range.yy - range.xx - 1));
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30