Submission #1238455

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

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 33, M = 2002;

int n;
int p[M][M];
int l2[M], r2[M];
int dp[N][N][N][N];

void maxh(int& x, int y)
{
    x = max(x, y);
}

int biggest_stadium(int N, std::vector<std::vector<int> > F)
{
    n = N;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            p[i][j] = p[i][j - 1] + F[i - 1][j - 1];
        }
    }

    int maxu = 0;
    int maxi = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (F[i - 1][j - 1] == 0)
            {
                l2[i] = j;
                break;
            }
        }
        for (int j = n; j >= 1; --j)
        {
            if (F[i - 1][j - 1] == 0)
            {
                r2[i] = j;
                break;
            }
        }
        if (p[i][r2[i]] - p[i][l2[i] - 1] > 0)
            return 0;
        if (r2[i] - l2[i] + 1 > maxu)
        {
            maxu = r2[i] - l2[i] + 1;
            maxi = i;
        }
    }
    int l0 = maxi;
    int r0 = maxi;
    int l = l2[maxi];
    int r = r2[maxi];
    while (1)
    {
        int sl0 = l0;
        int sr0 = r0;
        if (l2[l0 - 1])
        {
            if (l <= l2[l0 - 1] && r2[l0 - 1] <= r)
            {
                --l0;
                l = l2[l0];
                r = r2[l0];
            }
        }
        if (r2[r0 + 1])
        {
            if (l <= l2[r0 + 1] && r2[r0 + 1] <= r)
            {
                ++r0;
                l = l2[r0];
                r = r2[r0];
            }
        }
        if (m_p(l0, r0) == m_p(sl0, sr0))
            break;
    }
    for (int i = 1; i < l0; ++i)
    {
        if (l2[i])
            return 0;
    }
    for (int i = r0 + 1; i <= n; ++i)
    {
        if (r2[i])
            return 0;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += p[i][n];
    return ans;

    /*for (int i = 1; i <= n; ++i)
    {
        for (int l = 1; l <= n; ++l)
        {
            for (int r = l; r <= n; ++r)
            {
                if (p[i][r] - p[i][l - 1] == 0)
                    dp[i][i][l][r] = r - l + 1;
            }
        }
    }
    int ans = 0;
    for (int d0 = 1; d0 <= n; ++d0)
    {
        for (int l0 = 1; l0 + d0 - 1 <= n; ++l0)
        {
            int r0 = l0 + d0 - 1;
            for (int d = n; d >= 1; --d)
            {
                for (int l = 1; l + d - 1 <= n; ++l)
                {
                    int r = l + d - 1;
                    maxh(dp[l0][r0][l][r - 1], dp[l0][r0][l][r]);
                    maxh(dp[l0][r0][l + 1][r], dp[l0][r0][l][r]);

                    if (p[l0 - 1][r] - p[l0 - 1][l - 1] == 0)
                        maxh(dp[l0 - 1][r0][l][r], dp[l0][r0][l][r] + r - l + 1);

                    if (p[r0 + 1][r] - p[r0 + 1][l - 1] == 0)
                        maxh(dp[l0][r0 + 1][l][r], dp[l0][r0][l][r] + r - l + 1);

                    maxh(ans, dp[l0][r0][l][r]);
                }
            }
        }
    }

    return ans;*/
}

/*
5
1 1 1 1 1
1 1 1 1 1
1 0 0 1 1
1 0 0 0 1
1 1 0 0 1

5
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
*/

• 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