Submission #840884

#	Time	Username	Problem	Language	Result	Execution time	Memory
840884		emeraldblock	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2188 ms	436192 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using State = array<int,4>;
constexpr int NN = 2000;

template<>
struct std::hash<State> {
    size_t operator()(State const& a) const {
        return a[0]+NN*a[1]+1ll*NN*NN*a[2]+1ll*NN*NN*NN*a[3];
    }
};

int r2(int x) {
    return (31-__builtin_clz(x));
}

struct ST {
    int mx;
    array<vector<int>,11> data;
    ST() {}
    ST(vector<int> v, int _mx) : mx(_mx) {
        int n = v.size();
        data[0] = v;
        int w = 1;
        for (int i = 1; i < 11; ++i) {
            w *= 2;
            if (w > n) break;
            data[i].resize(n+1-w);
            for (int j = 0; j < n+1-w; ++j) {
                data[i][j] = min(data[i-1][j],data[i-1][j+w/2]);
            }
        }
    }
    int query(int l, int r) {
        if (l == r) return mx;
        int sz = r2(r-l);
        return min(data[sz][l],data[sz][r-(1<<sz)]);
    }
};

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    vector<int> row(N,0);
    vector<ST> up(N+1),down(N+1);
    for (int x = 0; x < N; ++x) {
        up[x] = ST(row,x);
        for (int y = 0; y < N; ++y) {
            row[y] = F[x][y] ? 0 : row[y]+1;
        }
    }
    up[N] = ST(row,N);
    fill(row.begin(),row.end(),0);
    down[N] = ST(row,0);
    for (int x = N-1; x >= 0; --x) {
        for (int y = 0; y < N; ++y) {
            row[y] = F[x][y] ? 0 : row[y]+1;
        }
        down[x] = ST(row,N-x);
    }
    vector<vector<int>> right(N,vector<int>(N+1));
    for (int x = 0; x < N; ++x) {
        right[x][N] = 1;
        for (int y = N-1; y >= 0; --y) {
            right[x][y] = F[x][y] ? 1 : right[x][y+1]+1;
        }
    }
    // {-l,r,u,d}
    unordered_map<State,int> dp;
    // {-l,r,u,d}
    priority_queue<State> pq;
    for (int x = 0; x <= N; ++x) {
        pq.push({-0,N,x,x});
    }
    int ans = 0;
    while (!pq.empty()) {
        auto t = pq.top(); pq.pop();
        ans = max(ans,dp[t]);
        auto [l,r,u,d] = t;
        l *= -1;
        if (u > 0) {
            int nl = l;
            while (true) {
                int nr = min(r,nl+right[u-1][nl]-1);
                int nu = u-up[u].query(nl,nr);
                int nd = d+down[d].query(nl,nr);
                State s = {-nl,nr,nu,nd};
                if (!dp.count(s)) {
                    pq.push(s);
                }
                dp[s] = max(dp[s],dp[t]+(nr-nl)*(nd-d+u-nu));
                nl = nr+1;
                if (nl > r) break;
            }
        }
        if (d < N) {
            int nl = l;
            while (true) {
                int nr = min(r,nl+right[d][nl]-1);
                int nu = u-up[u].query(nl,nr);
                int nd = d+down[d].query(nl,nr);
                State s = {-nl,nr,nu,nd};
                if (!dp.count(s)) {
                    pq.push(s);
                }
                dp[s] = max(dp[s],dp[t]+(nr-nl)*(nd-d+u-nu));
                nl = nr+1;
                if (nl > r) break;
            }
        }
    }
    return ans;
}

• 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