Submission #840498

#	Time	Username	Problem	Language	Result	Execution time	Memory
840498		danikoynov	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	3 ms	1036 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 31;
int dp[maxn][maxn][maxn][2], a[maxn][maxn], pref[maxn][maxn];

int biggest_stadium(int N, vector<vector<int>> F)
{
    for (int i = 1; i <= N; i ++)
        for (int j = 1; j <= N; j ++)
        {
            a[i][j] = F[i - 1][j - 1];
            pref[i][j] = pref[i][j - 1] + a[i][j];
        }


    int ans = 0;
    for (int i = 1; i <= N; i ++)
    {
         for (int j = 1; j <= N; j ++)
        {
              for (int k = j; k <= N; k ++)
            {
                   if (a[i][k] == 1)
                     break;
                /**int i = 1;
                int j = 2;
                int k = 5;*/
                for (int d = 1; d <= N; d ++)
                    for (int f = 1; f <= N; f ++)
                        for (int z = 1; z <= N; z ++)
                            dp[d][f][z][0] = dp[d][f][z][1] = 0;

                dp[i][j][k][0] = k - j + 1;
                dp[i][j][k][1] = k - j + 1;

                for (int len = 1; len <= N; len ++)
                    for (int f = 1; f <= N - len + 1; f ++)
                    {
                        int z = f + len - 1;
                        dp[i][f][z][0] = max(dp[i][f][z][0], dp[i][f + 1][z][0]);
                        dp[i][f][z][0] = max(dp[i][f][z][0], dp[i][f][z - 1][0]);
                    }

                for (int len = N; len > 0; len --)
                    for (int f = 1; f <= N - len + 1; f ++)
                    {
                        int z = f + len - 1;
                        dp[i][f][z][1] = max(dp[i][f][z][1], dp[i][f - 1][z][1]);
                        dp[i][f][z][1] = max(dp[i][f][z][1], dp[i][f][z + 1][1]);
                    }

                ans = max(ans, dp[i][j][k][0]);
                ///cout << "stop " << ans << endl;
                for (int d = i + 1; d <= N; d ++)
                {
                    for (int f = 1; f <= N; f ++)
                        for (int z = f; z <= N; z ++)
                        {
                            if (a[d][z] == 1)
                                break;
                            if ((f < j && z < k) ||
                                    (f > j && z > k))
                                continue;

                            dp[d][f][z][0] = dp[d - 1][f][z][0] + (z - f + 1);
                            dp[d][f][z][1] = dp[d - 1][f][z][1] + (z - f + 1);

                            dp[d][f][z][1] = max(dp[d][f][z][1], dp[d][f][z][0]);
                            ans = max(ans, dp[d][f][z][1]);

                            ///cout << "here " << d << " " << f << " " << z << " " << dp[d][f][z][0] << " " << dp[d][f][z][1] << endl;
                        }


                    for (int len = 1; len <= N; len ++)
                        for (int f = 1; f <= N - len + 1; f ++)
                        {
                            int z = f + len - 1;
                            dp[d][f][z][0] = max(dp[d][f][z][0], dp[d][f + 1][z][0]);
                            dp[d][f][z][0] = max(dp[d][f][z][0], dp[d][f][z - 1][0]);
                        }

                    for (int len = N; len > 0; len --)
                        for (int f = 1; f <= N - len + 1; f ++)
                        {
                            int z = f + len - 1;
                            dp[d][f][z][1] = max(dp[d][f][z][1], dp[d][f - 1][z][1]);
                            dp[d][f][z][1] = max(dp[d][f][z][1], dp[d][f][z + 1][1]);
                        }
                }



            }
        }


    }
    return ans;
}

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