Submission #1206309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206309		Nelt	Soccer Stadium (IOI23_soccer)	C++20	6 / 100	646 ms	169332 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
    a.insert(a.begin(), vector<int>(n + 1, 0));
    for (ll i = 1; i <= n; i++)
        a[i].insert(a[i].begin(), 0);
    ll pre[n + 2][n + 2], nxt[n + 2][n + 2], prer[n + 2][n + 2], nxtr[n + 2][n + 2];
    for (ll i = 0; i <= n + 1; i++)
        pre[0][i] = pre[i][0] = prer[0][i] = prer[i][0] = 0;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++)
            if (a[i][j])
                pre[i][j] = i, prer[i][j] = j;
            else
                pre[i][j] = pre[i - 1][j], prer[i][j] = prer[i][j - 1];
    for (ll i = 0; i <= n + 1; i++)
        nxt[n + 1][i] = nxt[i][n + 1] = nxtr[i][n + 1] = nxtr[n + 1][i] = n + 1;
    for (ll i = n; i >= 1; i--)
        for (ll j = n; j >= 1; j--)
            if (a[i][j])
                nxt[i][j] = i, nxtr[i][j] = j;
            else
                nxt[i][j] = nxt[i + 1][j], nxtr[i][j] = nxtr[i][j + 1];
    ll ans = 0;
    ll pref[n + 1], pref1[n + 1], suf[n + 1], suf1[n + 1];
    stack<ll> st, st1;
    for (ll r = 1; r <= n; r++)
    {
        while (!st.empty())
            st.pop();
        while (!st1.empty())
            st1.pop();
        pref[0] = pref1[0] = 0;
        st.push(0);
        st1.push(0);
        pre[r][0] = n + 1;
        nxt[r][0] = 0;
        for (ll i = 1; i <= n; i++)
        {
            while (!st.empty() and pre[r][st.top()] < pre[r][i])
                st.pop();
            while (!st1.empty() and nxt[r][st1.top()] > nxt[r][i])
                st1.pop();
            pref[i] = pref[st.top()] + (i - st.top()) * (r - pre[r][i]);
            pref1[i] = pref1[st1.top()] + (i - st1.top()) * (nxt[r][i] - r);
            st.push(i);
            st1.push(i);
        }
        while (!st.empty())
            st.pop();
        while (!st1.empty())
            st1.pop();
        st.push(n + 1);
        st1.push(n + 1);
        nxt[r][n + 1] = 0;
        pre[r][n + 1] = n + 1;
        suf[n + 1] = suf1[n + 1] = 0;
        for (ll i = n; i >= 1; i--)
        {
            while (!st.empty() and pre[r][st.top()] < pre[r][i])
                st.pop();
            while (!st1.empty() and nxt[r][st1.top()] > nxt[r][i])
                st1.pop();
            suf[i] = suf[st.top()] + (st.top() - i) * (r - pre[r][i]);
            suf1[i] = suf1[st1.top()] + (st1.top() - i) * (nxt[r][i] - r);
            st.push(i);
            st1.push(i);
        }
        for (ll i = 1; i <= n; i++)
        {
            ans = max(ans, pref[i] + suf[i] + pref1[i] + suf1[i] - (nxt[r][i] - pre[r][i] - 1) - (nxtr[r][i] - prer[r][i] - 1) - 1);
            // if (pref[i] + suf[i] + pref1[i] + suf1[i] - (nxt[r][i] - pre[r][i] - 1) - (nxtr[r][i] - prer[r][i] - 1) - 1 == 3)
            // {
            //     cout << pref[i] << " " << suf[i] << " " << pref1[i] << " " << suf1[i] << " " << nxt[r][i] - pre[r][i] - 1 << " " << nxtr[r][i] << " " << prer[r][i] << endl;
            // }
        }
    }
    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