Submission #842411

#	Time	Username	Problem	Language	Result	Execution time	Memory
842411		SHZhang	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	241 ms	32596 KiB

soccer

#include "soccer.h"

#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int top[2005][2005];
int bottom[2005][2005];
int rangetop[2005][2005], rangebottom[2005][2005];
int f[2005][2005];

const int inf = -100000000;

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int trees = 0, x = 0, y = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                trees++;
                x = i; y = j;
            }
        }
    }
    if (trees == 1) {
        return N * N - min(x+1, N-x) * min(y+1, N-y);
    }
    int widest_row = -1;
    int widest_cnt = 0;
    for (int i = 0; i < N; i++) {
        int emptycnt = 0;
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                top[i][j] = N;
            } else if (i == 0 || F[i-1][j]) {
                top[i][j] = i; emptycnt++;
            } else {
                top[i][j] = top[i-1][j]; emptycnt++;
            }
        }
        if (emptycnt >= widest_cnt) {
            widest_row = i;
            widest_cnt = emptycnt;
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                bottom[i][j] = -1;
            } else if (i == N - 1 || F[i+1][j]) {
                bottom[i][j] = i;
            } else {
                bottom[i][j] = bottom[i+1][j];
            }
        }
    }
    int ans = 0;
    for (int mrow = 0; mrow < N; mrow++) {
        if (N > 500 && mrow != widest_row) continue;
        for (int i = 0; i < N; i++) {
            rangetop[i][i] = top[mrow][i];
            rangebottom[i][i] = bottom[mrow][i];
            f[i][i] = bottom[mrow][i] - top[mrow][i] + 1;
            if (f[i][i] < 0) f[i][i] = -inf;
        }
        for (int siz = 2; siz <= N; siz++) {
            for (int i = 0; i <= N - siz; i++) {
                rangetop[i][i+siz-1] = max(rangetop[i+1][i+siz-1], top[mrow][i]);
                rangebottom[i][i+siz-1] = min(rangebottom[i+1][i+siz-1], bottom[mrow][i]);
                if (rangetop[i][i+siz-1] > rangebottom[i][i+siz-1]) {
                    f[i][i+siz-1] = -inf;
                } else {
                    f[i][i+siz-1] = max(f[i+1][i+siz-1], f[i][i+siz-2]) + rangebottom[i][i+siz-1] - rangetop[i][i+siz-1] + 1;
                    ans = max(ans, f[i][i+siz-1]);
                }
            }
        }
    }
    return ans;
}

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