oj.uz

Submission #1027858

# Submission time Handle Problem Language Result Execution time Memory
1027858 2024-07-19T10:42:46 Z Mr_Husanboy Soccer Stadium (IOI23_soccer) C++17
6 / 100
 421 ms 94744 KB 
#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 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 2 ms 604 KB ok
8 Correct 21 ms 6412 KB ok
9 Correct 421 ms 94744 KB ok

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 22.0

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

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 2 ms 604 KB ok
9 Correct 21 ms 6412 KB ok
10 Correct 421 ms 94744 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Incorrect 0 ms 348 KB wrong
14 Halted 0 ms 0 KB -