Submission #1213030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213030		Aviansh	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	0 ms	324 KiB

soccer

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int biggest_stadium(int n, vector<vector<int>> F) {
    vector<vector<int>> left(n, vector<int>(n, 0));
    vector<vector<int>> right(n, vector<int>(n, 0));
    vector<vector<int>> up(n, vector<int>(n, 0));
    vector<vector<int>> down(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (F[i][j] == 1) {
                left[i][j] = 0;
            } else {
                if (j == 0) {
                    left[i][j] = 1;
                } else {
                    left[i][j] = left[i][j-1] + 1;
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = n-1; j >= 0; j--) {
            if (F[i][j] == 1) {
                right[i][j] = 0;
            } else {
                if (j == n-1) {
                    right[i][j] = 1;
                } else {
                    right[i][j] = right[i][j+1] + 1;
                }
            }
        }
    }
    
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            if (F[i][j] == 1) {
                up[i][j] = 0;
            } else {
                if (i == 0) {
                    up[i][j] = 1;
                } else {
                    up[i][j] = up[i-1][j] + 1;
                }
            }
        }
    }
    
    for (int j = 0; j < n; j++) {
        for (int i = n-1; i >= 0; i--) {
            if (F[i][j] == 1) {
                down[i][j] = 0;
            } else {
                if (i == n-1) {
                    down[i][j] = 1;
                } else {
                    down[i][j] = down[i+1][j] + 1;
                }
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (F[i][j] == 0) {
                int horizontal_arm = left[i][j] + right[i][j] - 1;
                int vertical_arm = up[i][j] + down[i][j] - 1;
                int cross = horizontal_arm + vertical_arm - 1;
                ans = max(ans, cross);
            }
        }
    }
    
    vector<vector<int>> H(n, vector<int>(n, 0));
    for (int j = 0; j < n; j++) {
        if (F[0][j] == 0) {
            H[0][j] = 1;
        } else {
            H[0][j] = 0;
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (F[i][j] == 1) {
                H[i][j] = 0;
            } else {
                H[i][j] = H[i-1][j] + 1;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        stack<int> st;
        vector<int> left_index(n, 0);
        for (int j = 0; j < n; j++) {
            while (!st.empty() && H[i][st.top()] >= H[i][j]) {
                st.pop();
            }
            if (st.empty()) {
                left_index[j] = 0;
            } else {
                left_index[j] = st.top() + 1;
            }
            st.push(j);
        }
        
        while (!st.empty()) st.pop();
        
        vector<int> right_index(n, 0);
        for (int j = n-1; j >= 0; j--) {
            while (!st.empty() && H[i][st.top()] >= H[i][j]) {
                st.pop();
            }
            if (st.empty()) {
                right_index[j] = n-1;
            } else {
                right_index[j] = st.top() - 1;
            }
            st.push(j);
        }
        
        for (int j = 0; j < n; j++) {
            int width = right_index[j] - left_index[j] + 1;
            int area = H[i][j] * width;
            ans = max(ans, area);
        }
    }
    
    return ans;
}

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