Submission #1011988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011988		mdn2002	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	4269 ms	400416 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int dp[8000006];
int biggest_stadium(int N, vector<vector<int>> F) {
    int n = N;
    vector<vector<int>> a = F, next(n, vector<int>(n)), sum(n, vector<int>(n));
    map<vector<int>, int> mp;
    vector<vector<int>> v(n);
    set<pair<int, vector<int>>> vv;

    function<int(int, int, int, int)> summ = [&] (int l, int r, int x, int y) {
        long long ans = sum[y][r];
        if (x - 1 >= 0) ans -= sum[x - 1][r];
        if (l - 1 >= 0) ans -= sum[y][l - 1];
        if (x - 1 >= 0 && l - 1 >= 0) ans += sum[x - 1][l - 1];
        return ans;
    };

    int cnt = 0;

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            sum[i][j] += a[i][j];
            if (j) sum[i][j] += sum[i][j - 1];
            if (a[i][j] == 0) v[i].push_back(j);
        }
        v[i].push_back(n + 1);
    }
    for (int i = 1; i < n; i ++) {
        for (int j = 0; j < n; j ++) sum[i][j] += sum[i - 1][j];
    }
    for (int i = 0; i < n; i ++) {
        if (a[i][n - 1] == 0) next[i][n - 1] = n - 1;
        else next[i][n - 1] = n - 2;
        for (int j = n - 2; j >= 0; j --) {
            if (a[i][j]) next[i][j] = j - 1;
            else next[i][j] = next[i][j + 1];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (a[i][j]) continue;
            int ll = i, rr = n, mid, x, y;
            while (ll < rr) {
                mid = (ll + rr) / 2;
                if (summ(j, next[i][j], i, mid) == 0) ll = mid + 1;
                else rr = mid;
            }
            ll --;
            y = ll;

            ll = 0, rr = i;
            while (ll < rr) {
                mid = (ll + rr) / 2;
                if (summ(j, next[i][j], mid, i) == 0) rr = mid;
                else ll = mid + 1;
            }
            x = ll;
            vector<int> vvv = {j, next[i][j], x, y};
            if (mp[vvv] == 0) {
                vv.insert({-(next[i][j] - j), vvv});
                mp[vvv] = ++ cnt;
            }
            j = next[i][j];
        }
    }

    for (auto xxxx : vv) {
        auto [zzzz, xx] = xxxx;
        if (mp.count(xx) == 0) mp[xx] = ++ cnt;
        int id = mp[xx];
        dp[id] = max(dp[id], (xx[1] - xx[0] + 1) * (xx[3] - xx[2] + 1));
        ans = max(ans, dp[id]);

        int l = xx[0], r = xx[1], x = xx[2], y = xx[3];

        if (x - 1 >= 0) {
            for (int j = l; j <= r; j ++) {
                int z = min(r, next[x - 1][j]);
                if (a[x - 1][j] == 0) {

                    int ll = y, rr = n, mid, nx, ny;
                    while (ll < rr) {
                        mid = (ll + rr) / 2;
                        if (summ(j, z, x, mid) == 0) ll = mid + 1;
                        else rr = mid;
                    }
                    ll --;
                    ny = ll;

                    ll = 0, rr = x;
                    while (ll < rr) {
                        mid = (ll + rr) / 2;
                        if (summ(j, z, mid, y) == 0) rr = mid;
                        else ll = mid + 1;
                    }
                    nx = ll;

                    vector<int> xxx = {j, z, nx, ny};
                    if (mp.count(xxx) == 0) {
                        mp[xxx] = ++ cnt;
                        vv.insert({-(z - j), xxx});
                    }
                    int idd = mp[xxx];
                    dp[idd] = max(dp[idd], dp[id] + (z - j + 1) * (x - nx + ny - y));
                }
                j = *upper_bound(v[x - 1].begin(), v[x - 1].end(), z) - 1;
            }
        }
        if (y + 1 < n) {
            for (int j = l; j <= r; j ++) {
                int z = min(r, next[y + 1][j]);
                if (a[y + 1][j] == 0) {
                    int ll = y, rr = n, mid, nx, ny;
                    while (ll < rr) {
                        mid = (ll + rr) / 2;
                        if (summ(j, z, x, mid) == 0) ll = mid + 1;
                        else rr = mid;
                    }
                    ll --;
                    ny = ll;

                    ll = 0, rr = x;
                    while (ll < rr) {
                        mid = (ll + rr) / 2;
                        if (summ(j, z, mid, y) == 0) rr = mid;
                        else ll = mid + 1;
                    }
                    nx = ll;

                    vector<int> xxx = {j, z, nx, ny};
                    if (mp.count(xxx) == 0) {
                        mp[xxx] = ++ cnt;
                        vv.insert({-(z - j), xxx});
                    }
                    int idd = mp[xxx];
                    dp[idd] = max(dp[idd], dp[id] + (z - j + 1) * (x - nx + ny - y));
                }
                j = *upper_bound(v[y + 1].begin(), v[y + 1].end(), z) - 1;
            }
        }
    }
    return ans;
}
/*
3
0 0 1
0 0 0
1 0 0
*/

• 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