oj.uz

Submission #839754

# Submission time Handle Problem Language Result Execution time Memory
839754 2023-08-30T15:50:07 Z model_code Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 300 KB 
// correct/bf_rec.cpp

#include "soccer.h"
#include <iostream>

class solver
{
    int N;
    std::vector<std::vector<int>> C;
    int ans;

    void explore_stadium(int row, std::vector<std::pair<int, int>> hist, int currX, int currY, int state, int cells)
    {
        ans = std::max(ans, cells);
        if (row < N)
        {
            for (int j = 0; j < N; j++)
            {
                for (int k = j; k < N; k++)
                {
                    if (0 == C[row][k])
                    {
                        bool ok = true;
                        for (auto &[l, r] : hist)
                        {
                            ok &= (l <= j && k <= r) || (j <= l && r <= k);
                        }
                        if (!ok)
                            continue;
                        if (0 == state)
                        {
                            if (j <= currX && currY <= k)
                            {
                                auto nhist = hist;
                                nhist.push_back({j, k});
                                explore_stadium(row + 1, nhist, j, k, 0, cells + (k - j + 1));
                            }
                            else if (currX <= j && k <= currY)
                            {
                                auto nhist = hist;
                                nhist.push_back({j, k});
                                explore_stadium(row + 1, nhist, j, k, 1, cells + (k - j + 1));
                            }
                        }
                        else
                        {
                            if (currX <= j && k <= currY)
                            {
                                auto nhist = hist;
                                nhist.push_back({j, k});
                                explore_stadium(row + 1, nhist, j, k, 1, cells + (k - j + 1));
                            }
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    }

public:
    solver(int N, std::vector<std::vector<int>> C) : N(N), C(std::move(C)), ans(0) {}

    int solve()
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                for (int k = j; k < N; k++)
                {
                    if (0 == C[i][k])
                    {
                        explore_stadium(i + 1, {{j, k}}, j, k, 0, k - j + 1);
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        return ans;
    }
};

int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
    solver s(N, C);
    return s.solve();
}

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 1 ms 212 KB ok
3 Execution timed out 4524 ms 212 KB Time limit exceeded
4 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 1 ms 212 KB ok
3 Correct 1 ms 212 KB ok
4 Correct 0 ms 212 KB ok
5 Correct 1 ms 300 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 212 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 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 1 ms 300 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 1 ms 212 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
14 Correct 1 ms 212 KB ok
15 Correct 143 ms 280 KB ok
16 Correct 19 ms 296 KB ok
17 Correct 1 ms 300 KB ok
18 Correct 1 ms 212 KB ok
19 Correct 1 ms 212 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 212 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 1 ms 212 KB ok
24 Correct 1 ms 212 KB ok
25 Correct 1 ms 300 KB ok
26 Correct 4 ms 300 KB ok

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 1 ms 212 KB ok
4 Execution timed out 4524 ms 212 KB Time limit exceeded
5 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 1 ms 212 KB ok
4 Execution timed out 4524 ms 212 KB Time limit exceeded
5 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 1 ms 212 KB ok
4 Execution timed out 4524 ms 212 KB Time limit exceeded
5 Halted 0 ms 0 KB -