oj.uz

Submission #839766

# Submission time Handle Problem Language Result Execution time Memory
839766 2023-08-30T15:50:38 Z model_code Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 79076 KB 
// correct/authors_subtaskB5.cpp

// ##################################
// ##                              ##
// ##   Solution for Subtask B5    ##
// ##         (78.25 pts)          ##
// ##                              ##
// ##################################

#include <iostream>
#include <vector>
#include <algorithm>

#include "soccer.h"

using namespace std;

int solve(int N, vector<int> cl, vector<int> cr)
{
    vector<vector<int>> max_cl(N, vector<int>(N, (1 << 30)));
    vector<vector<int>> min_cr(N, vector<int>(N, (1 << 30)));

    // Calculate Min/Max
    for (int i = 0; i < N; i++)
    {
        int cur_cl = -(1 << 30), cur_cr = (1 << 30);
        for (int j = i; j < N; j++)
        {
            cur_cl = max(cur_cl, cl[j]);
            cur_cr = min(cur_cr, cr[j]);
            max_cl[i][j] = cur_cl;
            min_cr[i][j] = cur_cr;
        }
    }

    // Dynamic Programming
    vector<vector<int>> dp(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++)
    {
        dp[i][i] = (min_cr[i][i] - max_cl[i][i] + 1);
    }
    for (int len = 0; len < N - 1; len++)
    {
        for (int i = 0; i < N - len; i++)
        {
            int j = i + len;
            if (i >= 1)
                dp[i - 1][j] = max(dp[i - 1][j], dp[i][j] + (min_cr[i - 1][j] - max_cl[i - 1][j] + 1));
            if (j < N - 1)
                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + (min_cr[i][j + 1] - max_cl[i][j + 1] + 1));
        }
    }

    // Return
    return dp[0][N - 1];
}

int biggest_stadium(int N, vector<vector<int>> C)
{
    int Answer = 0;

    // Search "the red line"
    for (int i = 0; i <= N; i++)
    {
        vector<int> cl(N, i);
        vector<int> cr(N, i - 1);
        for (int j = 0; j < N; j++)
        {
            for (int k = i - 1; k >= 0; k--)
            {
                if (C[j][k] == 1)
                    break;
                cl[j] = k;
            }
            for (int k = i; k < N; k++)
            {
                if (C[j][k] == 1)
                    break;
                cr[j] = k;
            }
        }

        // Calculate DP
        int ret = solve(N, cl, cr);
        Answer = max(Answer, ret);
    }

    // Return
    return Answer;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB ok
6 Correct 0 ms 212 KB ok
7 Correct 6 ms 508 KB ok
8 Correct 771 ms 5488 KB ok
9 Execution timed out 4530 ms 79076 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 256 KB ok
9 Correct 1 ms 212 KB ok
10 Correct 1 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB ok
2 Correct 1 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 256 KB ok
10 Correct 1 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 1 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Correct 0 ms 212 KB ok
18 Correct 0 ms 212 KB ok
19 Correct 1 ms 212 KB ok
20 Correct 1 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 1 ms 212 KB ok
25 Correct 1 ms 212 KB ok
26 Correct 1 ms 212 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB ok
2 Correct 1 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 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 256 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 1 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Correct 1 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 1 ms 212 KB ok
22 Correct 1 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 1 ms 212 KB ok
27 Correct 1 ms 212 KB ok
28 Correct 1 ms 212 KB ok
29 Correct 1 ms 212 KB ok
30 Correct 1 ms 212 KB ok
31 Correct 1 ms 260 KB ok
32 Correct 1 ms 212 KB ok
33 Correct 0 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 1 ms 212 KB ok
36 Correct 1 ms 256 KB ok
37 Correct 1 ms 212 KB ok
38 Correct 1 ms 212 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 1 ms 212 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB ok
2 Correct 1 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 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 256 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 1 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Correct 1 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Correct 0 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 1 ms 212 KB ok
22 Correct 1 ms 212 KB ok
23 Correct 0 ms 212 KB ok
24 Correct 0 ms 212 KB ok
25 Correct 0 ms 212 KB ok
26 Correct 1 ms 212 KB ok
27 Correct 1 ms 212 KB ok
28 Correct 1 ms 212 KB ok
29 Correct 1 ms 212 KB ok
30 Correct 1 ms 212 KB ok
31 Correct 1 ms 260 KB ok
32 Correct 1 ms 212 KB ok
33 Correct 0 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 1 ms 212 KB ok
36 Correct 1 ms 256 KB ok
37 Correct 1 ms 212 KB ok
38 Correct 1 ms 212 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 0 ms 212 KB ok
41 Correct 1 ms 212 KB ok
42 Correct 784 ms 5416 KB ok
43 Correct 827 ms 5376 KB ok
44 Correct 829 ms 5484 KB ok
45 Correct 902 ms 5472 KB ok
46 Correct 767 ms 5416 KB ok
47 Correct 969 ms 5376 KB ok
48 Correct 739 ms 5392 KB ok
49 Correct 714 ms 5440 KB ok
50 Correct 769 ms 5512 KB ok
51 Correct 736 ms 5520 KB ok
52 Correct 750 ms 5476 KB ok
53 Correct 787 ms 5532 KB ok
54 Correct 765 ms 5580 KB ok
55 Correct 730 ms 5532 KB ok
56 Correct 736 ms 5460 KB ok
57 Correct 768 ms 5508 KB ok
58 Correct 804 ms 5496 KB ok
59 Correct 825 ms 5396 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB ok
2 Correct 1 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 1 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 6 ms 508 KB ok
9 Correct 771 ms 5488 KB ok
10 Execution timed out 4530 ms 79076 KB Time limit exceeded
11 Halted 0 ms 0 KB -