Submission #1056632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056632		mc061	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	4597 ms	348 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
const int mN = 50;
int pref[mN][mN]={};
int go_down[mN][mN]={};
int go_up[mN][mN]={};
int go_right[mN][mN]={};
int go_left[mN][mN]={};

int streak_top[mN]={};
int streak_bot[mN]={};
int streak_left[mN]={};
int streak_right[mN]={};

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    memset(go_down, 0, sizeof(go_down));
    memset(go_up, 0, sizeof(go_up));
    memset(go_right, 0, sizeof(go_right));
    memset(go_left, 0, sizeof(go_left));
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            pref[i][j] = F[i][j];
            if (i>0)
                pref[i][j] += pref[i-1][j];
            if (j > 0)
                pref[i][j] += pref[i][j-1];
            if (i > 0 && j > 0)
                pref[i][j] -= pref[i-1][j-1];
        }
    }
    auto q = [&] (int i1, int j1, int i2, int j2) -> int {
        int res = pref[i2][j2];
        if (i1 > 0) res -= pref[i1-1][j2];
        if (j1 > 0) res -= pref[i2][j1-1];
        if (i1 > 0 && j1 > 0) res += pref[i1-1][j1-1];
        return res;
    };

    for (int i = 0; i < N; ++i) {
        go_left[i][0] = 0;
        for (int j = 1; j < N; ++j) {
            go_left[i][j] = (F[i][j-1] == 0 ? go_left[i][j-1] + 1 : 0);
        }
        go_right[i][N-1] = 0;
        for (int j = N-2; j >= 0; --j) {
            go_right[i][j] = (F[i][j+1] == 0 ? go_right[i][j+1] + 1 : 0);
        }

        go_up[0][i] = 0;
        for (int j = 1; j < N; ++j) {
            go_up[j][i] = (F[j-1][i] == 0 ? go_up[j-1][i] + 1 : 0);
        }
        go_down[N-1][i] = 0;
        for (int j = N-2; j >= 0; --j) {
            go_down[j][i] = (F[j+1][i] == 0 ? go_down[j+1][i] + 1 : 0);
        }
    }

    auto solve_vert = [&] (int i1, int j1, int i2, int j2) -> int {
        int add = 0;
        int ret = 0;
        for (int peak = j1; peak <= j2; ++peak) {
            int tophere = go_up[i1][peak];
            int bothere = go_down[i2][peak];
            for (int j = peak-1; j >= j1; --j) {
                if (streak_top[j] > tophere) {
                    add -= streak_top[j] - tophere;
                    streak_top[j] = tophere;
                }
                if (streak_bot[j] > bothere) {
                    add -= streak_bot[j] - bothere;
                    streak_bot[j] = bothere;
                }
            }
            streak_top[peak] = tophere;
            streak_bot[peak] = bothere;
            add += tophere;
            add += bothere;
            ret = max(ret, add);
            int here = add;
            int ltop = streak_top[peak];
            int lbot = streak_bot[peak];
            for (int j = peak+1; j <= j2; ++j) {
                int atop = go_up[i1][j];
                int abot = go_down[i2][j];
                ltop = min(atop, ltop);
                lbot = min(abot, lbot);
                here += ltop;
                here += lbot;
                ret = max(ret, here);
            }
        }
        return ret;
    };

    auto solve_hor = [&] (int i1, int j1, int i2, int j2) -> int {
        int add = 0;
        int ret = 0;
        for (int peak = i1; peak <= i2; ++peak) {
            int left = go_left[peak][j1];
            int right = go_right[peak][j2];
            for (int i = peak-1; i >= i1; --i) {
                if (streak_left[i] > left) {
                    add -= streak_left[i] - left;
                    streak_left[i] = left;
                }
                if (streak_right[i] > right) {
                    add -= streak_right[i] - right;
                    streak_right[i] = right;
                }
            }
            streak_left[peak] = left;
            streak_right[peak] = right;
            add += left;
            add += right;
            ret = max(ret, add);
            int here = add;
            int lleft = streak_left[peak];
            int lright = streak_right[peak];
            for (int i = peak+1; i <= i2; ++i) {
                int aleft = go_left[i][j1];
                int aright = go_right[i][j2];
                lleft = min(aleft, lleft);
                lright = min(aright, lright);
                here += lleft;
                here += lright;
                ret = max(ret, here);
            }
        }
        return ret;
    };

    int res = 0;

    for (int i1 = 0; i1 < N; ++i1) {
        for (int j1 = 0; j1 < N; ++j1) {
            for (int i2 = i1; i2 < N; ++i2) {
                for (int j2 = j1; j2 < N; ++j2) {
                    if (q(i1, j1, i2, j2) > 0) continue;
                    int now = (i2-i1+1)*(j2-j1+1);
                    now += solve_hor(i1, j1, i2, j2);
                    now += solve_vert(i1, j1, i2, j2);
                    // cerr << i1 << " " << j1 << " " << i2 << " " << j2 << ": " << now << endl;
                    res = max(res, now);
                }
            }
        }
    }
    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