Submission #1096952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096952		azberjibiou	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	881 ms	94556 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
 
typedef long long ll;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
const int mxN=2055;
const int mxM=35000;
const int mxK=1000000000;
const int MOD=998244353;
const ll INF=1e17;
struct uf{
    int par[mxN], l[mxN], r[mxN];
    void init(int n){for(int i=0;i<=n;i++) par[i]=i, l[i]=r[i]=i;}
    int fp(int a){return par[a]==a ? a : par[a]=fp(par[a]);}
    void mrg(int a, int b){ // a -> b merge
        int p=fp(a), q=fp(b);
        l[q]=min(l[q], l[p]);
        r[q]=max(r[q], r[p]);
        par[p]=q;
    } 
};
int N;
int A[mxN][mxN], S[mxN][mxN];
int H[mxN];
int dp[mxN][mxN];
vector <pair<pii, int>> prop;
vector <pii> trash;
int ans;
void input(){
    cin >> N;
    for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) A[i][j]=1;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cin >> A[i][j];
}
void init(int n, vector <vector<int>> F){
    N=n;
    for(int i=0;i<=N+1;i++) for(int j=0;j<=N+1;j++) A[i][j]=1;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) A[i][j]=F[i-1][j-1];
}
void make_prefix_sum(){
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j]=S[i][j-1]+A[i][j];
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) S[i][j]+=S[i-1][j];
}
int sum(int x1, int x2, int y1, int y2){return S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];}
vector <int> ct[mxN];
uf U1;
pii expand(int yl, int yr, int xr, int h){
    int nyl=yl, nyr=yr;
    int s=nyr, e=N;
    while(s!=e){
        int mid=(s+e)/2;
        if(sum(xr-h+1, xr, yr+1, mid)==0) s=mid+1;
        else e=mid;
    }
    nyr=(sum(xr-h+1, xr, yr+1, s)==0 ? s : s-1);
    s=1, e=yl;
    while(s!=e){
        int mid=(s+e)/2;
        if(sum(xr-h+1, xr, mid, nyl-1)==0) e=mid;
        else s=mid+1;
    }
    nyl=s;
    return pii(nyl, nyr);
}
void sweep(){
    for(int i=N;i>=1;i--){
        //set H
        for(int j=1;j<=N;j++) H[j]--;
        for(int j=1;j<=N;j++){
            if(H[j]==-1){
                H[j]=0;
                while(A[i-H[j]][j]==0) H[j]++; // using x, y coordinate as math
            }
        }
        H[0]=H[N+1]=0;
        //sweep
        for(int j=0;j<=N;j++) ct[j].clear();
        for(int j=1;j<=N;j++) ct[H[j]].push_back(j);
        //for(int j=1;j<=N;j++) printf("H[%d]=%d\n", j, H[j]);
        U1.init(N);
        //propagation
        for(auto [lr, val] : prop){
            auto [l, r]=lr;
            dp[l][r]=max(dp[l][r], val);
        }
        prop.clear();
        for(int j=N;j>=1;j--){
            //printf("j=%d\n", j);
            for(int x : ct[j]){
                if(H[x]<=H[x-1]) U1.mrg(x-1, x);
                if(H[x]<=H[x+1]) U1.mrg(x+1, x);
            }
            for(int x : ct[j]) if(U1.fp(x)==x){
                int yl=U1.l[x], yr=U1.r[x], xr=i;
                //set dp to rectangle area
                dp[yl][yr]=max(dp[yl][yr], j*(yr-yl+1));
                trash.emplace_back(yl, yr);
                ans=max(ans, dp[yl][yr]);
                //printf("dp[%d][%d][%d]=%d\n", xr, yl, yr, dp[xr][pii(yl, yr)]);
                //(yl, yr, xr) -> (yl, yr, xr-1)
                if(j!=1){
                    auto [nyl, nyr]=expand(yl, yr, xr-1, j-1);
                    prop.emplace_back(pii(nyl, nyr), dp[yl][yr]+(yl-nyl+nyr-yr)*(j-1));
                    //printf("nyl, nyr, xr-1 = %d %d %d\n", nyl, nyr, xr-1);
                }
                // (yl, yr, xr) -> (yl-1, yr, xr) or (yl, yr+1, xr)
                int nh=max(H[yl-1], H[yr+1]);
                if(nh!=0){
                    auto [nyl, nyr]=expand(yl, yr, xr, nh);
                    dp[nyl][nyr]=max(dp[nyl][nyr], dp[yl][yr]+(yl-nyl+nyr-yr)*nh);
                    //printf("nyl, nyr, xr, nh = %d %d %d %d\n", nyl, nyr, xr, nh);
                }
            }
        }
        for(auto [l, r] : trash) dp[l][r]=0;
        trash.clear();
    }
}
int biggest_stadium(int n, std::vector<std::vector<int>> F)
{
    init(n, F);
    make_prefix_sum();
    sweep();
    return ans;
}
/*
int main()
{
    gibon
    input();
    make_prefix_sum();
    sweep();
    cout << 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