Submission #1341048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341048		karel	Soccer Stadium (IOI23_soccer)	C++20	16 / 100	4598 ms	63244 KiB

soccer

#include "soccer.h"
using namespace std;

typedef vector<int> vi;

int biggest_stadium(int N, vector<vector<int>> F)
{
    vector<vi> mn(N, vi(N)), mx(N, vi(N));

    for(int c= 0; c < N; c++)
    {
        mn[0][c] = 0;
        mx[N-1][c] = N-1;
    }

    for(int r = 1; r < N; r++)
    {
        for(int c= 0; c < N; c++)
        {
            if(F[r-1][c])
                mn[r][c] = r;
            else
                mn[r][c] = mn[r-1][c];
            
            int r2 = N-1-r;
            if(F[r2+1][c])
                mx[r2][c] = r2;
            else
                mx[r2][c] = mx[r2+1][c];
        }
    }

    int out = 0;

    for(int r = 0; r < N; r++)
    {
        for(int c= 0; c < N; c++)
        {
            vector<pair<int, int>> boundsl, boundsr;
            int mx0 = mx[r][c], mn0 = mn[r][c];
            int total = -(mx0-mn0+1);
            for(int c2 = c; c2 >= 0 && !F[r][c2]; c2--)
            {
                mx0 = min(mx0, mx[r][c2]);
                mn0 = max(mn0, mn[r][c2]);

                boundsl.emplace_back(mx0, mn0);
            }
            mx0 = mx[r][c], mn0 = mn[r][c];
            for(int c2 = c; c2 < N && !F[r][c2]; c2++)
            {
                mx0 = min(mx0, mx[r][c2]);
                mn0 = max(mn0, mn[r][c2]);

                boundsr.emplace_back(mx0, mn0);
            }
            while(!boundsl.empty() || !boundsr.empty())
            {
                if(boundsl.empty())
                {
                    auto [t, b] = boundsr.back();
                    boundsr.pop_back();
                    total += t-b+1;
                    continue;
                } else if (boundsr.empty()) {
                    auto [t, b] = boundsl.back();
                    boundsl.pop_back();
                    total += t-b+1;
                    continue;
                }

                auto [mx1, mn1] = boundsl.back();
                auto [mx2, mn2] = boundsr.back();
                if(mx1 >= mx2 && mn1 <= mn2)
                {
                    auto [t, b] = boundsr.back();
                    boundsr.pop_back();
                    total += t-b+1;
                } else if(mx2 >= mx1 && mn2 <= mn1) {
                    auto [t, b] = boundsl.back();
                    boundsl.pop_back();
                    total += t-b+1;
                } else {
                    //piemel
                    int totl = 0, cutl = 0, totr = 0, cutr = 0;
                    while(!(boundsl.back().first >= mx2 && boundsl.back().second <= mn2))
                    {
                        auto [mx3, mn3] = boundsl.back();
                        boundsl.pop_back();
                        totl += mx3-mn3-1;
                        cutl += min(mx3, mx2) - max(mn3, mn2) + 1;
                    }

                    while(!(boundsr.back().first >= mx1 && boundsr.back().second <= mn1))
                    {
                        auto [mx3, mn3] = boundsr.back();
                        boundsr.pop_back();
                        totr += mx3-mn3-1;
                        cutr += min(mx3, mx1) - max(mn3, mn1) + 1;
                    }

                    total += max(totl + cutr, cutl + totr);
                }
            }
            
            out = max(out, total);
        }
    }


    return out;
}

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