oj.uz

Submission #987073

# Submission time Handle Problem Language Result Execution time Memory
987073 2024-05-21T19:26:03 Z activedeltorre Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1735 ms 139312 KB 
#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);
        };
        for (int i = maxL; i >= 0; --i)
        {
            if (L + (1 << i) > R)
            {
                continue;
            }
            L += 1 << i;
            if (extendable(R))
                L -= 1 << i;
        }
        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 1 ms 344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 432 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 17 ms 3672 KB ok
9 Correct 268 ms 55444 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 344 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 1 ms 344 KB ok
13 Correct 1 ms 344 KB ok
14 Correct 1 ms 344 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 1 ms 548 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 1 ms 344 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 1 ms 432 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 600 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 344 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 344 KB ok
42 Correct 67 ms 6996 KB ok
43 Correct 90 ms 7768 KB ok
44 Correct 32 ms 4692 KB ok
45 Correct 26 ms 4196 KB ok
46 Correct 54 ms 6008 KB ok
47 Correct 19 ms 3800 KB ok
48 Correct 18 ms 3920 KB ok
49 Correct 19 ms 3924 KB ok
50 Correct 40 ms 3920 KB ok
51 Correct 31 ms 4944 KB ok
52 Correct 21 ms 4184 KB ok
53 Correct 19 ms 3932 KB ok
54 Correct 21 ms 3928 KB ok
55 Correct 20 ms 3924 KB ok
56 Correct 19 ms 3928 KB ok
57 Correct 66 ms 7892 KB ok
58 Correct 78 ms 8332 KB ok
59 Correct 82 ms 8788 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 432 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 17 ms 3672 KB ok
10 Correct 268 ms 55444 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 1 ms 344 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 344 KB ok
18 Correct 1 ms 344 KB ok
19 Correct 1 ms 344 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 1 ms 548 KB ok
26 Correct 1 ms 348 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 1 ms 344 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 348 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 432 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 1 ms 348 KB ok
43 Correct 1 ms 348 KB ok
44 Correct 1 ms 344 KB ok
45 Correct 1 ms 348 KB ok
46 Correct 1 ms 344 KB ok
47 Correct 67 ms 6996 KB ok
48 Correct 90 ms 7768 KB ok
49 Correct 32 ms 4692 KB ok
50 Correct 26 ms 4196 KB ok
51 Correct 54 ms 6008 KB ok
52 Correct 19 ms 3800 KB ok
53 Correct 18 ms 3920 KB ok
54 Correct 19 ms 3924 KB ok
55 Correct 40 ms 3920 KB ok
56 Correct 31 ms 4944 KB ok
57 Correct 21 ms 4184 KB ok
58 Correct 19 ms 3932 KB ok
59 Correct 21 ms 3928 KB ok
60 Correct 20 ms 3924 KB ok
61 Correct 19 ms 3928 KB ok
62 Correct 66 ms 7892 KB ok
63 Correct 78 ms 8332 KB ok
64 Correct 82 ms 8788 KB ok
65 Correct 1311 ms 106148 KB ok
66 Correct 1044 ms 102444 KB ok
67 Correct 599 ms 76428 KB ok
68 Correct 347 ms 57992 KB ok
69 Correct 606 ms 69484 KB ok
70 Correct 782 ms 79192 KB ok
71 Correct 312 ms 56840 KB ok
72 Correct 262 ms 55432 KB ok
73 Correct 288 ms 55636 KB ok
74 Correct 301 ms 55636 KB ok
75 Correct 290 ms 55444 KB ok
76 Correct 538 ms 55632 KB ok
77 Correct 561 ms 55700 KB ok
78 Correct 449 ms 65548 KB ok
79 Correct 415 ms 59716 KB ok
80 Correct 393 ms 58352 KB ok
81 Correct 540 ms 58516 KB ok
82 Correct 443 ms 62292 KB ok
83 Correct 701 ms 74404 KB ok
84 Correct 302 ms 55556 KB ok
85 Correct 311 ms 55380 KB ok
86 Correct 312 ms 55544 KB ok
87 Correct 319 ms 56620 KB ok
88 Correct 293 ms 55572 KB ok
89 Correct 271 ms 55380 KB ok
90 Correct 286 ms 55628 KB ok
91 Correct 286 ms 55444 KB ok
92 Correct 478 ms 67148 KB ok
93 Correct 496 ms 69264 KB ok
94 Correct 379 ms 59800 KB ok
95 Correct 368 ms 57936 KB ok
96 Correct 366 ms 57028 KB ok
97 Correct 325 ms 56728 KB ok
98 Correct 321 ms 56084 KB ok
99 Correct 1305 ms 120780 KB ok
100 Correct 1359 ms 118476 KB ok
101 Correct 1302 ms 112372 KB ok
102 Correct 1391 ms 118488 KB ok
103 Correct 1523 ms 129048 KB ok
104 Correct 1655 ms 133072 KB ok
105 Correct 1735 ms 136408 KB ok
106 Correct 1626 ms 139312 KB ok
107 Correct 1581 ms 138316 KB ok
108 Correct 525 ms 60952 KB ok
109 Correct 772 ms 52912 KB ok