oj.uz

Submission #839756

# Submission time Handle Problem Language Result Execution time Memory
839756 2023-08-30T15:50:13 Z model_code Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1807 ms 131132 KB 
// correct/sol_db_N2logN_2.cpp

#include "soccer.h"
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cassert>
#include <string.h>
#define xx first
#define yy second

using namespace std;
typedef pair<int, int> pii;
const int maxL = 10;
int N;

map<pair<int, pii>, int> dp;
vector<vector<int>> pre;

int query(int li, int lj, int ri, int rj)
{
    return pre[ri][rj] - (li ? pre[li - 1][rj] : 0) - (lj ? pre[ri][lj - 1] : 0) + (li && lj ? pre[li - 1][lj - 1] : 0);
}

pii calc_range(int i, int l, int r)
{
    int li = i - 1, ri = i;
    for (int j = maxL; j >= 0; --j)
    {
        while (li - (1 << j) >= 0 && query(li - (1 << j), l, i - 1, r) == 0)
        {
            li -= 1 << j;
        }
        while (ri + (1 << j) < N && query(i, l, ri + (1 << j), r) == 0)
        {
            ri += 1 << j;
        }
    }
    if (li >= 0 && query(li, l, i - 1, r) == 0)
        li--;
    if (ri < N && query(i, l, ri, r) == 0)
        ri++;
    return pii{li, ri};
}

int calc(int i, int l, int r)
{
    auto it = dp.find({i, {l, r}});
    if (it != dp.end())
    {
        return it->yy;
    }
    pii range = calc_range(i, l, r);
    if (i != range.xx + 1)
    {
        return calc(range.xx + 1, l, r);
    }
    int li = range.xx;
    int ri = range.yy;
    int res = 0;

    for (int L = l, R = l; R <= r; ++L, R = max(R, L))
    {
        auto extendable = [&](int R)
        {
            return (li >= 0 && query(li, L, i - 1, R) == 0) || (ri < N && query(i, L, ri, R) == 0);
        };
        if (!extendable(R))
        {
            continue;
        }
        for (int i = maxL; i >= 0; --i)
        {
            if (R + (1 << i) <= r && extendable(R + (1 << i)))
            {
                R += 1 << i;
            }
        }
        pii range = calc_range(i, L, R);
        res = max(res, calc(i, L, R) + (R - L + 1) * (li - range.xx + range.yy - ri));
        R++;
    }
    return dp[{i, {l, r}}] = res;
}

int biggest_stadium(int n, vector<vector<int>> C)
{
    N = n, pre = C;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            pre[i][j] += (j ? pre[i][j - 1] : 0);
        }
    }
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            pre[i][j] += (i ? pre[i - 1][j] : 0);
        }
    }
    int res = 0;
    for (int i = 0; i < N; ++i)
    {
        pii range = calc_range(i, 0, N - 1);
        res = max(res, calc(i, 0, N - 1) + N * (range.yy - range.xx - 1));
    }
    return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 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 1 ms 340 KB ok
8 Correct 24 ms 3284 KB ok
9 Correct 292 ms 47376 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 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 1 ms 212 KB ok
9 Correct 1 ms 296 KB ok
10 Correct 1 ms 300 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 0 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 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 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 0 ms 212 KB ok
9 Correct 1 ms 212 KB ok
10 Correct 1 ms 296 KB ok
11 Correct 1 ms 300 KB ok
12 Correct 0 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 212 KB ok
17 Correct 1 ms 212 KB ok
18 Correct 1 ms 212 KB ok
19 Correct 1 ms 300 KB ok
20 Correct 0 ms 212 KB ok
21 Correct 0 ms 304 KB ok
22 Correct 1 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 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 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 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 296 KB ok
13 Correct 1 ms 300 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 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 1 ms 300 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 304 KB ok
24 Correct 1 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 212 KB ok
32 Correct 1 ms 300 KB ok
33 Correct 1 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 1 ms 292 KB ok
36 Correct 1 ms 212 KB ok
37 Correct 1 ms 212 KB ok
38 Correct 1 ms 300 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 1 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 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 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 1 ms 212 KB ok
9 Correct 0 ms 212 KB ok
10 Correct 0 ms 212 KB ok
11 Correct 1 ms 212 KB ok
12 Correct 1 ms 296 KB ok
13 Correct 1 ms 300 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 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 1 ms 300 KB ok
22 Correct 0 ms 212 KB ok
23 Correct 0 ms 304 KB ok
24 Correct 1 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 212 KB ok
32 Correct 1 ms 300 KB ok
33 Correct 1 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 1 ms 292 KB ok
36 Correct 1 ms 212 KB ok
37 Correct 1 ms 212 KB ok
38 Correct 1 ms 300 KB ok
39 Correct 0 ms 212 KB ok
40 Correct 1 ms 212 KB ok
41 Correct 1 ms 212 KB ok
42 Correct 69 ms 6864 KB ok
43 Correct 75 ms 7472 KB ok
44 Correct 40 ms 4480 KB ok
45 Correct 33 ms 4052 KB ok
46 Correct 78 ms 5744 KB ok
47 Correct 19 ms 3668 KB ok
48 Correct 20 ms 3540 KB ok
49 Correct 20 ms 3668 KB ok
50 Correct 31 ms 3628 KB ok
51 Correct 33 ms 4692 KB ok
52 Correct 19 ms 3660 KB ok
53 Correct 22 ms 3704 KB ok
54 Correct 20 ms 3668 KB ok
55 Correct 22 ms 3620 KB ok
56 Correct 26 ms 3660 KB ok
57 Correct 76 ms 7708 KB ok
58 Correct 78 ms 8116 KB ok
59 Correct 81 ms 8656 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok
2 Correct 0 ms 212 KB ok
3 Correct 0 ms 212 KB ok
4 Correct 0 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 1 ms 340 KB ok
9 Correct 24 ms 3284 KB ok
10 Correct 292 ms 47376 KB ok
11 Correct 0 ms 212 KB ok
12 Correct 1 ms 212 KB ok
13 Correct 1 ms 212 KB ok
14 Correct 0 ms 212 KB ok
15 Correct 0 ms 212 KB ok
16 Correct 1 ms 212 KB ok
17 Correct 1 ms 296 KB ok
18 Correct 1 ms 300 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 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 300 KB ok
27 Correct 0 ms 212 KB ok
28 Correct 0 ms 304 KB ok
29 Correct 1 ms 212 KB ok
30 Correct 0 ms 212 KB ok
31 Correct 1 ms 212 KB ok
32 Correct 1 ms 212 KB ok
33 Correct 1 ms 212 KB ok
34 Correct 1 ms 212 KB ok
35 Correct 1 ms 212 KB ok
36 Correct 1 ms 212 KB ok
37 Correct 1 ms 300 KB ok
38 Correct 1 ms 212 KB ok
39 Correct 1 ms 212 KB ok
40 Correct 1 ms 292 KB ok
41 Correct 1 ms 212 KB ok
42 Correct 1 ms 212 KB ok
43 Correct 1 ms 300 KB ok
44 Correct 0 ms 212 KB ok
45 Correct 1 ms 212 KB ok
46 Correct 1 ms 212 KB ok
47 Correct 69 ms 6864 KB ok
48 Correct 75 ms 7472 KB ok
49 Correct 40 ms 4480 KB ok
50 Correct 33 ms 4052 KB ok
51 Correct 78 ms 5744 KB ok
52 Correct 19 ms 3668 KB ok
53 Correct 20 ms 3540 KB ok
54 Correct 20 ms 3668 KB ok
55 Correct 31 ms 3628 KB ok
56 Correct 33 ms 4692 KB ok
57 Correct 19 ms 3660 KB ok
58 Correct 22 ms 3704 KB ok
59 Correct 20 ms 3668 KB ok
60 Correct 22 ms 3620 KB ok
61 Correct 26 ms 3660 KB ok
62 Correct 76 ms 7708 KB ok
63 Correct 78 ms 8116 KB ok
64 Correct 81 ms 8656 KB ok
65 Correct 1332 ms 102516 KB ok
66 Correct 1119 ms 99508 KB ok
67 Correct 590 ms 72704 KB ok
68 Correct 370 ms 55408 KB ok
69 Correct 613 ms 66932 KB ok
70 Correct 814 ms 77596 KB ok
71 Correct 335 ms 52480 KB ok
72 Correct 297 ms 51916 KB ok
73 Correct 335 ms 52996 KB ok
74 Correct 314 ms 52708 KB ok
75 Correct 374 ms 51936 KB ok
76 Correct 509 ms 52656 KB ok
77 Correct 568 ms 50920 KB ok
78 Correct 452 ms 61968 KB ok
79 Correct 439 ms 54608 KB ok
80 Correct 353 ms 54312 KB ok
81 Correct 386 ms 53240 KB ok
82 Correct 422 ms 57640 KB ok
83 Correct 776 ms 70268 KB ok
84 Correct 309 ms 51300 KB ok
85 Correct 326 ms 50152 KB ok
86 Correct 305 ms 51068 KB ok
87 Correct 315 ms 52844 KB ok
88 Correct 295 ms 51696 KB ok
89 Correct 331 ms 49016 KB ok
90 Correct 375 ms 49932 KB ok
91 Correct 290 ms 50428 KB ok
92 Correct 544 ms 61820 KB ok
93 Correct 539 ms 65612 KB ok
94 Correct 394 ms 55260 KB ok
95 Correct 359 ms 51252 KB ok
96 Correct 402 ms 51088 KB ok
97 Correct 323 ms 49424 KB ok
98 Correct 318 ms 48096 KB ok
99 Correct 1244 ms 112960 KB ok
100 Correct 1285 ms 110488 KB ok
101 Correct 1306 ms 104340 KB ok
102 Correct 1383 ms 110552 KB ok
103 Correct 1377 ms 121152 KB ok
104 Correct 1671 ms 125120 KB ok
105 Correct 1807 ms 127992 KB ok
106 Correct 1618 ms 131132 KB ok
107 Correct 1470 ms 130484 KB ok
108 Correct 520 ms 52780 KB ok
109 Correct 640 ms 52680 KB ok