Submission #1209893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209893		user736482	Soccer Stadium (IOI23_soccer)	C++20	6 / 100	733 ms	143660 KiB

soccer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

vector<vector<ll>>rot(vector<vector<ll>>a){
    ll n=a.size();
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n/2;j++){
            swap(a[i][j],a[i][n-1-j]);
        }
    }
    return a;
}
vector<vector<ll>>rot2(vector<vector<ll>>a){
    ll n=a.size();
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n/2;j++){
            swap(a[j][i],a[n-j-1][i]);
        }
    }
    return a;
}
vector<vector<ll>>policz(vector<vector<ll>>in){
    ll n=in.size();
    ll mx[n+7][n+7];
    ll ans[n+7][n+7];
    for(ll i=0;i<=n;i++){
        mx[0][i]=i;
        mx[i][0]=0;
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            mx[i][j]=mx[i][j-1];
           // cout<<mx[i][j]<<" ";
            if(in[i-1][j-1])mx[i][j]=j;
            //cout<<mx[i][j]<<" " ;
        }
        //cout<<"\n";
    }
    //cout<<"\n";
    stack<pair<ll,ll>>st;
    for(ll i=0;i<=n;i++){
        ans[0][i]=0;
        st.push({mx[0][i],0});
        for(ll j=1;j<=n;j++){
            while(st.top().ff<mx[j][i])st.pop();
            ans[j][i]=ans[st.top().ss][i]+(j-st.top().ss)*(i-mx[j][i]);
            st.push({mx[j][i],j});
        }
        while(st.size())st.pop();
    }
    vector<vector<ll>>zwr;
    for(ll i=0;i<=n;i++){
        zwr.pb({});
        for(ll j=0;j<=n;j++){
            zwr.back().pb(ans[j][i]);
        }
    }
    return zwr;
}

void wyp(vector<vector<ll>>a){
    vector<ll> vec[a.size()+7];
    for(auto i : a){
        ll cnt=0;
        for(auto j : i){vec[cnt].pb(j);cnt++;}
    }
    for(ll i=0;i<a.size();i++){
        for(ll j : vec[i])cout<<j<<" ";
        cout<<"\n";
    }
}

int biggest_stadium(ll n,vector<vector<ll>>f){
    vector<vector<ll>>zwr[4];
    zwr[0]=policz(f);
    f=rot(f);
    zwr[1]=rot2(policz(f));
    f=rot2(f);
    zwr[2]=rot(rot2(policz(f)));
    f=rot(f);
    zwr[3]=rot(policz(f));
    f=rot2(f);
    ll ans=0;
    /*wyp(zwr[0]);
    cout<<"\n";
    wyp(zwr[1]);
    cout<<"\n";
    wyp(zwr[2]);
    cout<<"\n";
    wyp(zwr[3]);
    cout<<"\n";*/
    for(ll i=0;i<=n;i++){
        for(ll j=0;j<=n;j++)ans=max(ans,zwr[0][i][j]+zwr[1][i][j]+zwr[2][i][j]+zwr[3][i][j]);
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30