oj.uz

Submission #979974

# Submission time Handle Problem Language Result Execution time Memory
979974 2024-05-11T18:10:42 Z vjudge1 Soccer Stadium (IOI23_soccer) C++17
13.5 / 100
 1 ms 600 KB 
// 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(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(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]!=-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];
    }
    //for(auto u:c)cout<<u<<' ';cout<<"\n";
    
    res.pb(dp);
    fo(i,0,n-1) if(A[i][p]) ans=max(ans, dp[i]),dp[i]=tt[i]=0;
    
    //fo(i,0,n)cout<<tt[i]<<' ';cout<<"\n";
    
    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);
    
    for(auto u:dp)ans=max(u,ans);
    
    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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Incorrect 1 ms 348 KB wrong
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 600 KB ok
6 Correct 1 ms 600 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 600 KB ok
7 Correct 1 ms 600 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Partially correct 0 ms 348 KB partial
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 344 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 1 ms 348 KB wrong
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 1 ms 348 KB wrong
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 1 ms 348 KB wrong
5 Halted 0 ms 0 KB -