Submission #1081066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081066		asdasdqwer	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	693 ms	102548 KiB

soccer

#include "soccer.h"

#include <bits/stdc++.h>
using namespace std;

#define pii array<int, 2>

vector<int> hlp(vector<int> &height) {
    stack<pii> s;
    s.push({height[0], 1});
    int ar = height[0];
    vector<int> ret(height.size());
    ret[0] = ar;
    for (int i=1;i<(int)height.size();i++) {
        int cnt=1;
        while (s.size() && height[i] <= s.top()[0]) {
            auto [he, nm] = s.top();s.pop();
            ar -= he * nm;
            cnt += nm;
        }
        ar += cnt * height[i];
        s.push({height[i], cnt});
        ret[i] = ar;
    }
    return ret;
}

int calc(vector<int> &height) {
    vector<int> v1 = hlp(height);
    reverse(height.begin(), height.end());
    vector<int> v2 = hlp(height);
    reverse(height.begin(), height.end());

    int n = (int)height.size();

    int mx = 0;
    reverse(v2.begin(), v2.end());
    for (int i=0;i<n;i++) {
        mx = max(mx, v1[i]+v2[i]-height[i]);
    }
    return mx;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    vector<vector<int>> up(N, vector<int>(N, 0));
    vector<vector<int>> dw = up, lf = up, rt = up;

    for (int i=0;i<N;i++) {
        if (F[i][0] == 0) {
            lf[i][0] = 1;
        }

        for (int j=1;j<N;j++) {
            if (F[i][j] == 1) lf[i][j] = 0;
            else lf[i][j] = lf[i][j-1] + 1;
        }

        if (F[i][N-1] == 0) rt[i][N-1] = 1;

        for (int j=N-2;j>=0;j--) {
            if (F[i][j] == 1) rt[i][j] = 0;
            else rt[i][j] = rt[i][j+1]+1;
        }
    }

    for (int j=0;j<N;j++) {
        if (F[0][j] == 0) up[0][j] = 1;
        for (int i=1;i<N;i++) {
            up[i][j] = up[i-1][j]+1;
            if (F[i][j] == 1) up[i][j]=0;
        }

        if (F[N-1][j] == 0) dw[N-1][j]=1;
        for (int i=N-2;i>=0;i--) {
            dw[i][j] = dw[i+1][j]+1;
            if (F[i][j] == 1) dw[i][j]=0;
        }
    }

    // for (int i=0;i<N;i++) {
    //     for (int j=0;j<N;j++) {
    //         cout << dw[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    // cout << "here " << endl;

    int ans = 0;

    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            if (F[i][j] == 1) continue;
            int k = j;
            vector<int> f1, f2;
            for (;k<N&&F[i][k]!=1;k++) {
                f1.push_back(up[i][k]);
                f2.push_back(dw[i][k]);
            }
            ans = max(ans, max(calc(f1), calc(f2)));
            j = k-1;
        }
    }

    for (int j=0;j<N;j++) {
        for (int i=0;i<N;i++) {
            if (F[i][j] == 1) continue;
            int k = i;
            vector<int> f1, f2;
            for (;k<N&&F[k][j]!=1;k++) {
                f1.push_back(rt[k][j]);
                f2.push_back(lf[k][j]);
            }
            ans = max(ans, max(calc(f1), calc(f2)));
            i = k-1;
        }
    }

    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