oj.uz

Submission #839751

# Submission time Handle Problem Language Result Execution time Memory
839751 2023-08-30T15:50:02 Z model_code Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 51608 KB 
// correct/BM_bigRec_N4log.cpp

#include "soccer.h"

#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int N, maxi, where;
int F[2502][2502];
int bMost[2502];
int id[2502];
set<int> block;
set<pair<pair<pair<int, int>, pair<int, int>>, int>> ans;
int val[2502 * 2502];

bool small(int x, int y)
{
    return bMost[x] > bMost[y];
}

int biggest_stadium(int NN, std::vector<std::vector<int>> FF)
{
    N = NN;
    N += 2;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            F[i][j] = 1;
        id[i] = i;
    }

    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
            F[i][j] = FF[i - 1][j - 1];
    }

    bMost[0] = -1;
    bMost[N - 1] = -1;

    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
        {
            if (F[i][j] == 1)
                bMost[j] = i;
        }
        std::sort(id + 1, id + N - 1, small);
        block.clear();
        block.insert(0);
        block.insert(N - 1);

        for (int j = 1; j < N - 1; j++)
        {
            int pos = id[j];
            if (bMost[pos] != i)
            {
                auto it = block.lower_bound(pos);
                int b = (*it);
                it--;
                int a = (*it);
                int v = i - bMost[pos], h = b - a - 1;
                if (bMost[a] != bMost[pos] && bMost[b] != bMost[pos])
                {
                    ans.insert({{{h, v}, {a + 1, bMost[pos] + 1}}, where});
                    val[where++] = v * h;
                }
            }
            block.insert(pos);
        }
    }

    for (auto i : ans)
    {
        maxi = val[i.second];
        for (auto j : ans)
        {
            if (j.first.first.first == i.first.first.first)
                break;

            if (i.first.second.first <= j.first.second.first && j.first.second.first + j.first.first.first - 1 <= i.first.second.first + i.first.first.first - 1)
            {
                if (i.first.second.second >= j.first.second.second && j.first.second.second + j.first.first.second - 1 >= i.first.second.second + i.first.first.second - 1)
                {
                    maxi = max(maxi, val[i.second] + val[j.second] - i.first.first.second * j.first.first.first);
                }
            }
        }
        val[i.second] = maxi;
    }

    maxi = 0;
    for (int i = 0; i < where; i++)
        maxi = max(maxi, val[i]);
    return maxi;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.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 340 KB ok
4 Correct 0 ms 340 KB ok
5 Correct 1 ms 212 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 2 ms 852 KB ok
8 Correct 52 ms 5352 KB ok
9 Correct 859 ms 51608 KB ok

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 1 ms 212 KB ok
7 Correct 0 ms 212 KB ok
8 Correct 0 ms 244 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 340 KB ok
13 Correct 1 ms 340 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 1 ms 212 KB ok
8 Correct 0 ms 212 KB ok
9 Correct 0 ms 244 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 340 KB ok
14 Correct 1 ms 340 KB ok
15 Correct 0 ms 340 KB ok
16 Correct 0 ms 340 KB ok
17 Correct 1 ms 304 KB ok
18 Correct 1 ms 308 KB ok
19 Correct 1 ms 308 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Correct 0 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Correct 1 ms 340 KB ok
25 Correct 1 ms 340 KB ok
26 Correct 0 ms 340 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 0 ms 340 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 1 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 244 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 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 0 ms 340 KB ok
19 Correct 1 ms 304 KB ok
20 Correct 1 ms 308 KB ok
21 Correct 1 ms 308 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Correct 0 ms 340 KB ok
25 Correct 0 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 1 ms 340 KB ok
28 Correct 0 ms 340 KB ok
29 Correct 0 ms 340 KB ok
30 Correct 2 ms 436 KB ok
31 Correct 2 ms 468 KB ok
32 Correct 1 ms 468 KB ok
33 Correct 1 ms 340 KB ok
34 Correct 1 ms 340 KB ok
35 Correct 1 ms 340 KB ok
36 Correct 1 ms 340 KB ok
37 Correct 1 ms 432 KB ok
38 Correct 1 ms 432 KB ok
39 Correct 1 ms 516 KB ok
40 Correct 1 ms 340 KB ok
41 Correct 2 ms 468 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 0 ms 340 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 1 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 0 ms 244 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 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 0 ms 340 KB ok
19 Correct 1 ms 304 KB ok
20 Correct 1 ms 308 KB ok
21 Correct 1 ms 308 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Correct 0 ms 340 KB ok
25 Correct 0 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 1 ms 340 KB ok
28 Correct 0 ms 340 KB ok
29 Correct 0 ms 340 KB ok
30 Correct 2 ms 436 KB ok
31 Correct 2 ms 468 KB ok
32 Correct 1 ms 468 KB ok
33 Correct 1 ms 340 KB ok
34 Correct 1 ms 340 KB ok
35 Correct 1 ms 340 KB ok
36 Correct 1 ms 340 KB ok
37 Correct 1 ms 432 KB ok
38 Correct 1 ms 432 KB ok
39 Correct 1 ms 516 KB ok
40 Correct 1 ms 340 KB ok
41 Correct 2 ms 468 KB ok
42 Execution timed out 4565 ms 18396 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 1 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 1 ms 212 KB ok
7 Correct 1 ms 212 KB ok
8 Correct 2 ms 852 KB ok
9 Correct 52 ms 5352 KB ok
10 Correct 859 ms 51608 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 0 ms 212 KB ok
14 Correct 1 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 0 ms 244 KB ok
17 Correct 1 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Correct 1 ms 212 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 1 ms 340 KB ok
22 Correct 0 ms 340 KB ok
23 Correct 0 ms 340 KB ok
24 Correct 1 ms 304 KB ok
25 Correct 1 ms 308 KB ok
26 Correct 1 ms 308 KB ok
27 Correct 1 ms 340 KB ok
28 Correct 0 ms 340 KB ok
29 Correct 0 ms 340 KB ok
30 Correct 0 ms 340 KB ok
31 Correct 1 ms 340 KB ok
32 Correct 1 ms 340 KB ok
33 Correct 0 ms 340 KB ok
34 Correct 0 ms 340 KB ok
35 Correct 2 ms 436 KB ok
36 Correct 2 ms 468 KB ok
37 Correct 1 ms 468 KB ok
38 Correct 1 ms 340 KB ok
39 Correct 1 ms 340 KB ok
40 Correct 1 ms 340 KB ok
41 Correct 1 ms 340 KB ok
42 Correct 1 ms 432 KB ok
43 Correct 1 ms 432 KB ok
44 Correct 1 ms 516 KB ok
45 Correct 1 ms 340 KB ok
46 Correct 2 ms 468 KB ok
47 Execution timed out 4565 ms 18396 KB Time limit exceeded
48 Halted 0 ms 0 KB -