oj.uz

Submission #840498

# Submission time Handle Problem Language Result Execution time Memory
840498 2023-08-31T12:42:13 Z danikoynov Soccer Stadium (IOI23_soccer) C++17
8 / 100
 3 ms 1036 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 340 KB ok
4 Correct 1 ms 372 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Runtime error 3 ms 1036 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 0 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 212 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 1 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 1 ms 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 1 ms 340 KB ok
18 Correct 1 ms 340 KB ok
19 Correct 0 ms 340 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Incorrect 0 ms 340 KB wrong
23 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 1 ms 372 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 1 ms 340 KB ok
18 Correct 1 ms 340 KB ok
19 Correct 1 ms 340 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Incorrect 0 ms 340 KB wrong
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 1 ms 372 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 0 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 212 KB ok
17 Correct 1 ms 340 KB ok
18 Correct 1 ms 340 KB ok
19 Correct 1 ms 340 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Incorrect 0 ms 340 KB wrong
25 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 1 ms 372 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Runtime error 3 ms 1036 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -