Submission #1027858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027858		Mr_Husanboy	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	421 ms	94744 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){return a.size();}



int biggest_stadium(int n, vector<vector<int>> f)
{

    vector uplef(n, vector(n, 0)), uprig(n, vector(n, 0));
    vector dolef(n, vector(n, 0)), dorig(n, vector(n, 0));
    vector<int> con(n, 0);
    int emp = 0;
    for(int j = 0; j < n; j ++){
        for(int i = 0; i < n; i ++){
            if(f[i][j]){
                con[i] = 0;
            }else{
                emp ++;
                con[i] ++;
            }
        }
        vector<int> near(n), st;
        for(int i = 0; i < n; i ++){
            while(!st.empty() && con[st.back()] >= con[i]) st.pop_back();
            if(st.empty()) near[i] = -1;
            else near[i] = st.back();
            st.push_back(i);
        }
        for(int i = 0; i < n; i ++){
            uplef[i][j] = con[i] * (i - near[i]);
            if(near[i] != -1){
                uplef[i][j] += uplef[near[i]][j];
            }
        }
    }   
    con.assign(n, 0);
    for(int j = n - 1; j >= 0; j --){
        for(int i = 0; i < n; i ++){
            if(f[i][j]){
                con[i] = 0;
            }else con[i] ++;
        }
        vector<int> near(n), st;
        for(int i = 0; i < n; i ++){
            while(!st.empty() && con[st.back()] >= con[i]) st.pop_back();
            if(st.empty()) near[i] = -1;
            else near[i] = st.back();
            st.push_back(i);
        }
        for(int i = 0; i < n; i ++){
            uprig[i][j] = con[i] * (i - near[i]);
            if(near[i] != -1){
                uprig[i][j] += uprig[near[i]][j];
            }
        }
    }
    con.assign(n, 0);
    for(int j = n - 1; j >= 0; j --){
        for(int i = n - 1; i >= 0; i --){
            if(f[i][j]){
                con[i] = 0;
            }else con[i] ++;
        }
        vector<int> near(n), st;
        for(int i = n - 1; i >= 0; i --){
            while(!st.empty() && con[st.back()] >= con[i]) st.pop_back();
            if(st.empty()) near[i] = n;
            else near[i] = st.back();
            st.push_back(i);
        }
        for(int i = n - 1; i >= 0; i --){
            dorig[i][j] = con[i] * (near[i] - i);
            if(near[i] != n){
                dorig[i][j] += dorig[near[i]][j];
            }
        }
    }
    con.assign(n, 0);
    for(int j = 0; j < n; j ++){
        for(int i = 0; i < n; i ++){
            if(f[i][j]){
                con[i] = 0;
            }else con[i] ++;
        }
        vector<int> near(n), st;
        for(int i = n - 1; i >= 0; i --){
            while(!st.empty() && con[st.back()] >= con[i]) st.pop_back();
            if(st.empty()) near[i] = n;
            else near[i] = st.back();
            st.push_back(i);
        }
        for(int i = n - 1; i >= 0; i --){
            dolef[i][j] = con[i] * (near[i] - i);
            if(near[i] != n){
                dolef[i][j] += dolef[near[i]][j];
            }
        }
    }
    int ans = 0;
    
    for(int j = 0; j < n; j ++){
        for(int i = 0; i < n; i ++){
            int cnt = uplef[i][j];
            if(j + 1 < n){
                cnt += uprig[i][j + 1];
            }
            if(i + 1 < n){
                cnt += dolef[i + 1][j];
            }
            if(i + 1 < n && j + 1 < n){
                cnt += dorig[i + 1][j + 1];
            }
            ans = max(ans, cnt);
        }
    }

    if(ans < emp){
        return ans;
    }
    vector<pair<int,int>> a(n);
    int mx = 0;
    for(int i = 0; i < n; i ++){
        a[i].ff = n, a[i].ss = 0;
        for(int j = 0; j < n; j ++){
            if(f[i][j] == 0){
                a[i].ff = min(a[i].ff, j);
                a[i].ss = max(a[i].ss, j);
            }
        }
        mx = max(mx, a[i].ss - a[i].ff + 1);
    }
    int mid = 0;
    for(int i = 0; i < n; i ++){
        if(mx == a[i].ss - a[i].ff + 1){
            mid = i; break;
        }
    }
    int l = mid, r = mid;

    while(r < n && l >= 0){
        while(l >= 0 && a[l].ff <= a[r].ff && a[r].ss <= a[l].ss){
            l --;
        }
        if(l >= 0 && not(a[r].ff <= a[l].ff && a[l].ss <= a[r].ss)){
            return ans;
        }
        r ++;
    }

    return emp;
}

• 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