oj.uz

Submission #1018587

# Submission time Handle Problem Language Result Execution time Memory
1018587 2024-07-10T07:14:29 Z tinjyu Soccer Stadium (IOI23_soccer) C++17
48 / 100
 74 ms 114032 KB 
#include "soccer.h"
#include <iostream>
long long int dp[105][105][505];
long long int dp_left[105][505][505], dp_right[105][105][505];
long long int left_bound[505][505], right_bound[505][505];

using namespace std;

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{

    long long int ans = 0;
    for (int i = 0; i < N; i++)
    {
        int lf = -1;
        for (int j = 0; j < N; j++)
        {
            if (F[i][j] == 1)
            {
                lf = j;
            }
            left_bound[i][j] = lf;
        }
        int rf = N;
        for (int j = N - 1; j >= 0; j--)
        {
            if (F[i][j] == 1)
            {
                rf = j;
            }
            right_bound[i][j] = rf;
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (F[i][j] == 1)
            {
                dp[i][i][j] = -1;
            }
            else
            {
                dp[i][i][j] = right_bound[i][j] - left_bound[i][j] - 1;
                dp_left[i][i][j] = left_bound[i][j];
                dp_right[i][i][j] = right_bound[i][j];
            }
            ans = max(ans, dp[i][i][j]);
        }
    }

    for (int len = 2; len <= N; len++)
    {
        for (int i = 0; i + len - 1 < N; i++)
        {
            for (int col = 0; col < N; col++)
            {

                int up = i, down = i + len - 1;
                // cout << dp[up][down][col] << " " << up << " " << down << " " << col << endl;

                if (F[up][col] == 0)
                {
                    int lf = max(dp_left[up + 1][down][col], left_bound[up][col]);
                    int ri = min(dp_right[up + 1][down][col], right_bound[up][col]);
                    dp[up][down][col] = dp[up + 1][down][col] + ri - lf - 1;
                    dp_left[up][down][col] = lf;
                    dp_right[up][down][col] = ri;
                }
                if (F[down][col] == 0)
                {
                    int lf = max(dp_left[up][down - 1][col], left_bound[down][col]);
                    int ri = min(dp_right[up][down - 1][col], right_bound[down][col]);
                    if (dp[up][down - 1][col] + ri - lf - 1 > dp[up][down][col])
                    {

                        dp[up][down][col] = max(dp[up][down - 1][col] + ri - lf - 1, dp[up][down][col]);
                        dp_left[up][down][col] = lf;
                        dp_right[up][down][col] = ri;
                    }
                }
                // cout << dp[up][down][col] << " " << up << " " << down << " " << col << endl;
                ans = max(ans, dp[up][down][col]);
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 3 ms 29172 KB ok
4 Correct 4 ms 33116 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 28 ms 80892 KB ok
8 Runtime error 73 ms 114032 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 2 ms 14684 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 2 ms 14680 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 ms 14964 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 2 ms 14680 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 14684 KB ok
14 Correct 2 ms 14684 KB ok
15 Correct 3 ms 24924 KB ok
16 Correct 3 ms 24924 KB ok
17 Correct 3 ms 25020 KB ok
18 Correct 3 ms 24924 KB ok
19 Correct 3 ms 22876 KB ok
20 Correct 2 ms 16824 KB ok
21 Correct 2 ms 25020 KB ok
22 Correct 3 ms 24924 KB ok
23 Correct 3 ms 18876 KB ok
24 Correct 2 ms 18780 KB ok
25 Correct 2 ms 20964 KB ok
26 Correct 3 ms 24924 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 3 ms 29172 KB ok
5 Correct 4 ms 33116 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 ms 14680 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 2 ms 14964 KB ok
11 Correct 2 ms 14684 KB ok
12 Correct 2 ms 14684 KB ok
13 Correct 2 ms 14680 KB ok
14 Correct 2 ms 12636 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14684 KB ok
17 Correct 3 ms 24924 KB ok
18 Correct 3 ms 24924 KB ok
19 Correct 3 ms 25020 KB ok
20 Correct 3 ms 24924 KB ok
21 Correct 3 ms 22876 KB ok
22 Correct 2 ms 16824 KB ok
23 Correct 2 ms 25020 KB ok
24 Correct 3 ms 24924 KB ok
25 Correct 3 ms 18876 KB ok
26 Correct 2 ms 18780 KB ok
27 Correct 2 ms 20964 KB ok
28 Correct 3 ms 24924 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 5 ms 54624 KB ok
31 Correct 6 ms 56796 KB ok
32 Correct 7 ms 56668 KB ok
33 Correct 6 ms 52624 KB ok
34 Correct 5 ms 48772 KB ok
35 Correct 6 ms 44216 KB ok
36 Correct 5 ms 45916 KB ok
37 Correct 5 ms 45708 KB ok
38 Correct 5 ms 45924 KB ok
39 Correct 5 ms 48216 KB ok
40 Correct 5 ms 48476 KB ok
41 Correct 6 ms 33884 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 3 ms 29172 KB ok
5 Correct 4 ms 33116 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 ms 14680 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 2 ms 14964 KB ok
11 Correct 2 ms 14684 KB ok
12 Correct 2 ms 14684 KB ok
13 Correct 2 ms 14680 KB ok
14 Correct 2 ms 12636 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14684 KB ok
17 Correct 3 ms 24924 KB ok
18 Correct 3 ms 24924 KB ok
19 Correct 3 ms 25020 KB ok
20 Correct 3 ms 24924 KB ok
21 Correct 3 ms 22876 KB ok
22 Correct 2 ms 16824 KB ok
23 Correct 2 ms 25020 KB ok
24 Correct 3 ms 24924 KB ok
25 Correct 3 ms 18876 KB ok
26 Correct 2 ms 18780 KB ok
27 Correct 2 ms 20964 KB ok
28 Correct 3 ms 24924 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 5 ms 54624 KB ok
31 Correct 6 ms 56796 KB ok
32 Correct 7 ms 56668 KB ok
33 Correct 6 ms 52624 KB ok
34 Correct 5 ms 48772 KB ok
35 Correct 6 ms 44216 KB ok
36 Correct 5 ms 45916 KB ok
37 Correct 5 ms 45708 KB ok
38 Correct 5 ms 45924 KB ok
39 Correct 5 ms 48216 KB ok
40 Correct 5 ms 48476 KB ok
41 Correct 6 ms 33884 KB ok
42 Runtime error 74 ms 109916 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB ok
2 Correct 2 ms 14684 KB ok
3 Correct 2 ms 14684 KB ok
4 Correct 3 ms 29172 KB ok
5 Correct 4 ms 33116 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 28 ms 80892 KB ok
9 Runtime error 73 ms 114032 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -