Submission #840586

#	Time	Username	Problem	Language	Result	Execution time	Memory
840586		blackyuki	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	1082 ms	691148 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define fi first
#define se second
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    ll n=N+2;
    vvi v(n,vi(n,1));
    rep(i,N)rep(j,N)v[i+1][j+1]=F[i][j];
    vvvi next(2,vvi(n,vi(n,n))),prev(2,vvi(n,vi(n,-1)));
    rep(i,n)rep(j,n){
        prev[v[i][j]][i][j]=j;
        if(j>0)prev[1-v[i][j]][i][j]=prev[1-v[i][j]][i][j-1];
    }
    rep(i,n)for(int j=n-1;j>=0;j--){
        next[v[i][j]][i][j]=j;
        if(j<n-1)next[1-v[i][j]][i][j]=next[1-v[i][j]][i][j+1];
    }
    vvi up(n,vi(n)),down(n,vi(n)),upl(n,vi(n,-1)),upr(n,vi(n,-1)),downl(n,vi(n,n)),downr(n,vi(n,n));
    rep(i,n)rep(j,n){
        if(v[i][j])up[i][j]=i+1;
        else up[i][j]=up[i-1][j];
    }
    for(int i=n-1;i>=0;i--)rep(j,n){
        if(v[i][j])down[i][j]=i-1;
        else down[i][j]=down[i+1][j];
    }
    rep(i,n)rep(j,n)if(!v[i][j]){
        chmax(upl[i][j],up[i][j]);
        upl[i][j+1]=upl[i][j];
        chmin(downl[i][j],down[i][j]);
        downl[i][j+1]=downl[i][j];
    }
    rep(i,n)for(ll j=n-1;j>=0;j--)if(!v[i][j]){
        chmax(upr[i][j],up[i][j]);
        upr[i][j-1]=upr[i][j];
        chmin(downr[i][j],down[i][j]);
        downr[i][j-1]=downr[i][j];
    }
    vector<vector<map<P,ll>>> dp(n,vector<map<P,ll>>(n));
    rep(i,n)REP(j,1,n-1)if(v[i][j-1]&&!v[i][j]){
        ll l=j,r=next[1][i][j]-1;
        ll u=upr[i][j],d=downr[i][j];
        if(u==i)dp[l][r][P(u,d)]=(r-l+1)*(d-u+1);
    }
    auto f1=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=upr[u-1][l],nd=d;
        if(next[1][d+1][l]>r+1)return;
        if(next[1][d+1][l]==r+1)nd=downr[d+1][l];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    auto f2=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=upl[u-1][r],nd=d;
        if(prev[1][d+1][r]<l-1)return;
        if(prev[1][d+1][r]==l-1)nd=downl[d+1][r];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    auto f3=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=u,nd=downr[d+1][l];
        if(next[1][u-1][l]>r+1)return;
        if(next[1][u-1][l]==r+1)nd=upr[u-1][l];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    auto f4=[&](ll u,ll d,ll l,ll r,ll x){
        ll nu=u,nd=downl[d+1][r];
        if(prev[1][u-1][r]<l-1)return;
        if(prev[1][u-1][r]==l-1)nd=upl[u-1][r];
        chmax(dp[l][r][P(nu,nd)],x+(r-l+1)*(nd-nu+u-d));
    };
    ll ans=0;
    rep(l,n)for(ll r=n-1;r>=l;r--){
        for(auto x:dp[l][r]){
            chmax(ans,x.se);
            ll u=x.fi.fi,d=x.fi.se;
            ll cur=l;
            if(!v[u-1][l]){
                f1(u,d,l,next[1][u-1][l]-1,x.se);
                cur=next[1][u-1][l];
            }
            while(true){
                cur=next[0][u-1][cur];
                if(cur>r)break;
                ll t=next[1][u-1][cur];
                if(t>r){
                    f2(u,d,cur,r,x.se);
                    break;
                }
                f1(u,d,cur,next[1][u-1][cur]-1,x.se);
                cur=next[1][u-1][cur];
            }
            cur=l;
            if(!v[d+1][l]){
                f3(u,d,l,next[1][d+1][l]-1,x.se);
                cur=next[1][d+1][l];
            }
            while(true){
                cur=next[0][d+1][cur];
                if(cur>r)break;
                ll t=next[1][d+1][cur];
                if(t>r){
                    f4(u,d,cur,r,x.se);
                    break;
                }
                f3(u,d,cur,next[1][d+1][cur]-1,x.se);
                cur=next[1][d+1][cur];
            }
        }
    }
    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