Submission #1033196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033196		TAhmed33	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	1466 ms	335604 KiB

soccer

#include "soccer.h"
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e3 + 25;
const int M = (1 << 30) - 1;
const int B = 1e5 + 4;
int n, a[MAXN][MAXN], pref[MAXN][MAXN], pre[MAXN][MAXN];
int sparse[MAXN][11][MAXN];
int query (int x1, int y1, int x2, int y2) {
    return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}
struct custom_hash {
    size_t operator()(array <int, 4> x) const {
        return ((x[0] + x[1] * B + x[2] * B * B + x[3] * B * B * B) % M + M) % M;
    }
};
unordered_map <array <int, 4>, int, custom_hash> memo;
int query (int j, int l, int r) {
    int x = __lg(r - l + 1);
    return min(sparse[j][x][l], sparse[j][x][r - (1 << x) + 1]);
}
int get (int l, int r, int x, int y) {
    int R = r;
    int ans = r + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (query(x, mid, R) < y) {
            l = mid + 1;
        } else {
            r = mid - 1; ans = mid;
        }
    }
    return ans;
}
int get2 (int l, int r, int x, int y) {
    int L = l;
    int ans = l - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (query(x, L, mid) < y) {
            r = mid - 1;
        } else {
            l = mid + 1; ans = mid;
        }
    }
    return ans;
}
int ans (int x, int y, int l, int r) {
    if (memo.count({x, y, l, r})) {
        return memo[{x, y, l, r}];
    }
    int ret = 0;
    for (int i = l; i <= r; i++) {
        if (x != 1 && !a[x - 1][i]) {
            if (i > l && !a[x - 1][i - 1]) {
                continue;
            }
            int j = min(r + 1, pre[x - 1][i]);
            int g = get(1, x - 1, i, j);
            int h = get2(y + 1, n, i, j);
            ret = max(ret, (j - i) * (x - g + h - y) + ans(g, h, i, j - 1));
            i = j;
        }
    }
    for (int i = l; i <= r; i++) {
        if (y != n && !a[y + 1][i]) {
            if (i > l && !a[y + 1][i - 1]) {
                continue;
            }
            int j = min(r + 1, pre[y + 1][i]);
            int g = get(1, x - 1, i, j);
            int h = get2(y + 1, n, i, j);
            ret = max(ret, (j - i) * (x - g + h - y) + ans(g, h, i, j - 1));
            i = j;
        }
    }
    return memo[{x, y, l, r}] = ret;
}
int biggest_stadium (int _N, vector <vector <int>> _F) {
    //start with explaining the 25% solution
    n = _N;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = _F[i - 1][j - 1];
            pref[i][j] = a[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        int z = n + 1;
        for (int j = n; j >= 1; j--) {
            if (a[i][j]) {
                z = j;
            }
            pre[i][j] = z;
        }
    }
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            sparse[j][0][i] = pre[i][j];
        }
        for (int k = 1; k < 11; k++) {
            for (int i = 1; i + (1 << k) - 1 <= n; i++) {
                sparse[j][k][i] = min(sparse[j][k - 1][i], sparse[j][k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j]) {
                continue;
            }
            if (j > 1 && !a[i][j - 1]) {
                continue;
            }
            ret = max(ret, (pre[i][j] - j) + ans(i, i, j, pre[i][j] - 1));
        }
    }
    return ret;
}

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