oj.uz

Submission #1018597

# Submission time Handle Problem Language Result Execution time Memory
1018597 2024-07-10T07:18:21 Z tinjyu Soccer Stadium (IOI23_soccer) C++17
64 / 100
 440 ms 104532 KB 
#include "soccer.h"
#include <iostream>
long long int dp[505][2][505];
long long int dp_left[505][2][505], dp_right[505][2][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;
        }
    }
    int now = 1, pre = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (F[i][j] == 1)
            {
                dp[i][0][j] = -1;
            }
            else
            {
                dp[i][0][j] = right_bound[i][j] - left_bound[i][j] - 1;
                dp_left[i][0][j] = left_bound[i][j];
                dp_right[i][0][j] = right_bound[i][j];
            }
            ans = max(ans, dp[i][0][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][pre][col], left_bound[up][col]);
                    int ri = min(dp_right[up + 1][pre][col], right_bound[up][col]);
                    dp[up][now][col] = dp[up + 1][pre][col] + ri - lf - 1;
                    dp_left[up][now][col] = lf;
                    dp_right[up][now][col] = ri;
                }
                if (F[down][col] == 0)
                {
                    int lf = max(dp_left[up][pre][col], left_bound[down][col]);
                    int ri = min(dp_right[up][pre][col], right_bound[down][col]);
                    if (dp[up][pre][col] + ri - lf - 1 > dp[up][now][col])
                    {

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

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8636 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 4 ms 14936 KB ok
8 Correct 254 ms 18832 KB ok
9 Runtime error 293 ms 104532 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8640 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8640 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8536 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8636 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8536 KB ok
23 Correct 1 ms 8540 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8636 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8640 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8640 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8536 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8636 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8540 KB ok
24 Correct 1 ms 8536 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8540 KB ok
29 Correct 1 ms 8536 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8540 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 8536 KB ok
34 Correct 1 ms 8540 KB ok
35 Correct 1 ms 8540 KB ok
36 Correct 1 ms 8540 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8540 KB ok
39 Correct 1 ms 8540 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8788 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8636 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8640 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8640 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8536 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8636 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8540 KB ok
24 Correct 1 ms 8536 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8540 KB ok
29 Correct 1 ms 8536 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8540 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 8536 KB ok
34 Correct 1 ms 8540 KB ok
35 Correct 1 ms 8540 KB ok
36 Correct 1 ms 8540 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 8540 KB ok
39 Correct 1 ms 8540 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8788 KB ok
42 Correct 349 ms 18820 KB ok
43 Correct 440 ms 18780 KB ok
44 Correct 337 ms 18828 KB ok
45 Correct 311 ms 18804 KB ok
46 Correct 310 ms 18824 KB ok
47 Correct 272 ms 18724 KB ok
48 Correct 176 ms 18824 KB ok
49 Correct 204 ms 18776 KB ok
50 Correct 222 ms 18780 KB ok
51 Correct 295 ms 18780 KB ok
52 Correct 119 ms 18704 KB ok
53 Correct 96 ms 14720 KB ok
54 Correct 119 ms 18780 KB ok
55 Correct 141 ms 18836 KB ok
56 Correct 179 ms 18704 KB ok
57 Correct 282 ms 18780 KB ok
58 Correct 262 ms 18824 KB ok
59 Correct 303 ms 18828 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8636 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 4 ms 14936 KB ok
9 Correct 254 ms 18832 KB ok
10 Runtime error 293 ms 104532 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -