Submission #1238414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238414		SamAnd	축구 경기장 (IOI23_soccer)	C++20	0 / 100	77 ms	13640 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 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];
        }
    }

    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 0 1 1
1 1 0 0 1
1 1 1 0 1
1 1 1 1 1
1 1 1 1 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