Submission #979981

#	Time	Username	Problem	Language	Result	Execution time	Memory
979981		vjudge1	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	776 ms	83432 KiB

soccer

// hola soy Dember :D
// 31/03/2024

#include <bits/stdc++.h>

#define ll int 
#define pll pair<ll,ll>
#define F first
#define S second 
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z

using namespace std;

void value(ll in){cout<<((in)?"YES\n":"NO\n");}

ll n, m, k, xd[2006], zd[2006], tt[2006];
ll ans;
vector<vector<ll>> iz, A, res;
vector<ll> dp;
vector<pll> r;
set<ll> f;
queue<ll> q;

vector<ll> cl(ll p){
    vector<ll> st, v(n+1);
    ll x;
    fo(i,0,n-1)v[i]=i;
    
    fo(i,0,n-1){
        x=i;
        
        while(!st.empty() && iz[st.back()][p]<=iz[i][p]){x=st.back();st.pop_back();}
        
        st.push_back(i);
        v[i]=v[x];
    }
    return v;
}

vector<ll> cr(ll p){
    vector<ll> st, v(n+1);
    ll x;
    fo(i,0,n-1)v[i]=i;
    
    of(i,n-1,0){
        x=i;
        
        while(!st.empty() && iz[st.back()][p]<=iz[i][p]){x=st.back();st.pop_back();}
        
        st.push_back(i);
        v[i]=v[x];
    }
    return v;
}

void CD(ll p){
    vector<ll> a, b, c(n+1), d;r.clear();
    
    a=cl(p);
    b=cr(p);
    
    fo(i,0,n-1)c[i]=b[i]-a[i]+1;
    
    fo(i,0,n-1){
        if(!A[i][p])r.pb({iz[i][p], i});
        xd[i]=i-1;zd[i]=i+1;
    }zd[n-1]=-1;
    
    sort(all(r));
    
    for(auto u:r)dp[u.S]+=(c[u.S]-tt[u.S])*(p-iz[u.S][p]);
    
    for(auto u:r){
        if(xd[u.S]>=0)dp[xd[u.S]]=max(dp[xd[u.S]],(c[xd[u.S]]-c[u.S])*(p-iz[xd[u.S]][p])+dp[u.S]);
        if(zd[u.S]>=0)dp[zd[u.S]]=max(dp[zd[u.S]],(c[zd[u.S]]-c[u.S])*(p-iz[zd[u.S]][p])+dp[u.S]);
        if(zd[u.S]!=-1)xd[zd[u.S]]=xd[u.S];
        if(xd[u.S]!=-1)zd[xd[u.S]]=zd[u.S];
        
        tt[u.S]=c[u.S];
    }
    
    res.pb(dp);
    for(auto u:dp)ans=max(ans, u);
    fo(i,0,n-1) if(A[i][p])dp[i]=tt[i]=0;
    
    return;
}

int biggest_stadium(int N, vector<vector<int>> ola){
    n=N;iz.resize(n+1,vector<ll>(n+1,-1));A=ola;dp.resize(n+1,0);
    
    fo(i,0,n-1){
        fo(j,0,n-1){
            if(A[i][j])iz[i][j]=j;
            else if(j>0)iz[i][j]=iz[i][j-1];
        }
    }
    
    of(h,n-1,0)CD(h);
    
    return ans;
}

/*int main()
{
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    
    int t=1; 
    cin>>t;
    
    vector<vector<int>> ola(t+1,vector<int> (t+1));
    fo(i,0,t-1)
        fo(j,0,t-1)cin>>ola[i][j];
    
    cout<<biggest_stadium(t, ola)<<"\n";
    
    fo(i,0,n-1){
        fo(j,0,n-1)cout<<res[i][j]<<' ';cout<<"\n";
    }

    return 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