Submission #1238378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238378		SamAnd	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	2876 ms	993688 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 = 502, M = 2002;

int n;
int p[M][M];
int dp1[N][N][N], dp2[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];
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int d = 1; d <= n; ++d)
        {
            for (int l = 1; l + d - 1 <= n; ++l)
            {
                int r = l + d - 1;
                maxh(dp1[i - 1][l - 1][r], dp1[i - 1][l][r]);
                maxh(dp1[i - 1][l][r + 1], dp1[i - 1][l][r]);
            }
        }
        for (int l = 1; l <= n; ++l)
        {
            for (int r = l; r <= n; ++r)
            {
                if (p[i][r] - p[i][l - 1] == 0)
                    maxh(dp1[i][l][r], dp1[i - 1][l][r] + r - l + 1);
            }
        }
    }
    for (int i = n; i >= 1; --i)
    {
        for (int d = 1; d <= n; ++d)
        {
            for (int l = 1; l + d - 1 <= n; ++l)
            {
                int r = l + d - 1;
                maxh(dp2[i + 1][l - 1][r], dp2[i + 1][l][r]);
                maxh(dp2[i + 1][l][r + 1], dp2[i + 1][l][r]);
            }
        }
        for (int l = 1; l <= n; ++l)
        {
            for (int r = l; r <= n; ++r)
            {
                if (p[i][r] - p[i][l - 1] == 0)
                    maxh(dp2[i][l][r], dp2[i + 1][l][r] + r - l + 1);
            }
        }
    }

    int ans = 0;
    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)
                    maxh(ans, dp1[i - 1][l][r] + dp2[i + 1][l][r] + r - l + 1);
            }
        }
    }
    return ans;
}

/*
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