oj.uz

Submission #839771

# Submission time Handle Problem Language Result Execution time Memory
839771 2023-08-30T15:50:48 Z model_code Soccer Stadium (IOI23_soccer) C++17
64 / 100
 885 ms 1071292 KB 
// correct/sol_db_N3_1.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 maxN = 501;
int N, dp[maxN][maxN][maxN];

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;
    while (li >= 0 && query(li, l, i - 1, r) == 0)
        li--;
    while (ri < N && query(i, l, ri, r) == 0)
        ri++;
    return pii{li, ri};
}

int calc(int i, int l, int r)
{
    if (dp[i][l][r] != -1)
    {
        return dp[i][l][r];
    }
    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;
        }
        while (R + 1 <= r && extendable(R + 1))
            R++;

        int Li = li;
        int Ri = ri;
        while (Li >= 0 && query(Li, L, i - 1, R) == 0)
            Li--;
        while (Ri < N && query(i, L, Ri, R) == 0)
            Ri++;

        res = max(res, calc(i, L, R) + (R - L + 1) * (li - Li + Ri - 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);
        }
    }
    memset(dp, -1, sizeof dp);
    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 172 ms 492452 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 492396 KB ok
2 Correct 161 ms 492456 KB ok
3 Correct 164 ms 492372 KB ok
4 Correct 200 ms 492396 KB ok
5 Correct 182 ms 492436 KB ok
6 Correct 197 ms 492408 KB ok
7 Correct 183 ms 492560 KB ok
8 Correct 192 ms 495656 KB ok
9 Runtime error 885 ms 1071292 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 492396 KB ok
2 Correct 161 ms 492456 KB ok
3 Correct 152 ms 492388 KB ok
4 Correct 150 ms 492344 KB ok
5 Correct 146 ms 492440 KB ok
6 Correct 164 ms 492372 KB ok
7 Correct 147 ms 492440 KB ok
8 Correct 170 ms 492400 KB ok
9 Correct 164 ms 492460 KB ok
10 Correct 153 ms 492356 KB ok
11 Correct 147 ms 492444 KB ok
12 Correct 163 ms 492468 KB ok
13 Correct 147 ms 492452 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492452 KB ok
2 Correct 167 ms 492396 KB ok
3 Correct 161 ms 492456 KB ok
4 Correct 152 ms 492388 KB ok
5 Correct 150 ms 492344 KB ok
6 Correct 146 ms 492440 KB ok
7 Correct 164 ms 492372 KB ok
8 Correct 147 ms 492440 KB ok
9 Correct 170 ms 492400 KB ok
10 Correct 164 ms 492460 KB ok
11 Correct 153 ms 492356 KB ok
12 Correct 147 ms 492444 KB ok
13 Correct 163 ms 492468 KB ok
14 Correct 147 ms 492452 KB ok
15 Correct 156 ms 492364 KB ok
16 Correct 157 ms 492492 KB ok
17 Correct 265 ms 492388 KB ok
18 Correct 171 ms 492344 KB ok
19 Correct 153 ms 492424 KB ok
20 Correct 155 ms 492352 KB ok
21 Correct 165 ms 492460 KB ok
22 Correct 180 ms 492452 KB ok
23 Correct 149 ms 492364 KB ok
24 Correct 210 ms 492380 KB ok
25 Correct 177 ms 492460 KB ok
26 Correct 163 ms 492536 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492452 KB ok
2 Correct 167 ms 492396 KB ok
3 Correct 161 ms 492456 KB ok
4 Correct 164 ms 492372 KB ok
5 Correct 200 ms 492396 KB ok
6 Correct 152 ms 492388 KB ok
7 Correct 150 ms 492344 KB ok
8 Correct 146 ms 492440 KB ok
9 Correct 164 ms 492372 KB ok
10 Correct 147 ms 492440 KB ok
11 Correct 170 ms 492400 KB ok
12 Correct 164 ms 492460 KB ok
13 Correct 153 ms 492356 KB ok
14 Correct 147 ms 492444 KB ok
15 Correct 163 ms 492468 KB ok
16 Correct 147 ms 492452 KB ok
17 Correct 156 ms 492364 KB ok
18 Correct 157 ms 492492 KB ok
19 Correct 265 ms 492388 KB ok
20 Correct 171 ms 492344 KB ok
21 Correct 153 ms 492424 KB ok
22 Correct 155 ms 492352 KB ok
23 Correct 165 ms 492460 KB ok
24 Correct 180 ms 492452 KB ok
25 Correct 149 ms 492364 KB ok
26 Correct 210 ms 492380 KB ok
27 Correct 177 ms 492460 KB ok
28 Correct 163 ms 492536 KB ok
29 Correct 218 ms 492484 KB ok
30 Correct 185 ms 492368 KB ok
31 Correct 167 ms 492464 KB ok
32 Correct 216 ms 492392 KB ok
33 Correct 172 ms 492428 KB ok
34 Correct 166 ms 492464 KB ok
35 Correct 159 ms 492396 KB ok
36 Correct 156 ms 492356 KB ok
37 Correct 174 ms 492424 KB ok
38 Correct 278 ms 492400 KB ok
39 Correct 207 ms 492388 KB ok
40 Correct 190 ms 492464 KB ok
41 Correct 169 ms 492348 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492452 KB ok
2 Correct 167 ms 492396 KB ok
3 Correct 161 ms 492456 KB ok
4 Correct 164 ms 492372 KB ok
5 Correct 200 ms 492396 KB ok
6 Correct 152 ms 492388 KB ok
7 Correct 150 ms 492344 KB ok
8 Correct 146 ms 492440 KB ok
9 Correct 164 ms 492372 KB ok
10 Correct 147 ms 492440 KB ok
11 Correct 170 ms 492400 KB ok
12 Correct 164 ms 492460 KB ok
13 Correct 153 ms 492356 KB ok
14 Correct 147 ms 492444 KB ok
15 Correct 163 ms 492468 KB ok
16 Correct 147 ms 492452 KB ok
17 Correct 156 ms 492364 KB ok
18 Correct 157 ms 492492 KB ok
19 Correct 265 ms 492388 KB ok
20 Correct 171 ms 492344 KB ok
21 Correct 153 ms 492424 KB ok
22 Correct 155 ms 492352 KB ok
23 Correct 165 ms 492460 KB ok
24 Correct 180 ms 492452 KB ok
25 Correct 149 ms 492364 KB ok
26 Correct 210 ms 492380 KB ok
27 Correct 177 ms 492460 KB ok
28 Correct 163 ms 492536 KB ok
29 Correct 218 ms 492484 KB ok
30 Correct 185 ms 492368 KB ok
31 Correct 167 ms 492464 KB ok
32 Correct 216 ms 492392 KB ok
33 Correct 172 ms 492428 KB ok
34 Correct 166 ms 492464 KB ok
35 Correct 159 ms 492396 KB ok
36 Correct 156 ms 492356 KB ok
37 Correct 174 ms 492424 KB ok
38 Correct 278 ms 492400 KB ok
39 Correct 207 ms 492388 KB ok
40 Correct 190 ms 492464 KB ok
41 Correct 169 ms 492348 KB ok
42 Correct 198 ms 495760 KB ok
43 Correct 230 ms 495684 KB ok
44 Correct 198 ms 495708 KB ok
45 Correct 234 ms 495768 KB ok
46 Correct 198 ms 495784 KB ok
47 Correct 178 ms 495784 KB ok
48 Correct 187 ms 495588 KB ok
49 Correct 202 ms 495712 KB ok
50 Correct 374 ms 495700 KB ok
51 Correct 202 ms 495784 KB ok
52 Correct 195 ms 495756 KB ok
53 Correct 170 ms 495872 KB ok
54 Correct 189 ms 495752 KB ok
55 Correct 207 ms 495708 KB ok
56 Correct 175 ms 495776 KB ok
57 Correct 352 ms 495852 KB ok
58 Correct 337 ms 495752 KB ok
59 Correct 396 ms 495852 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492452 KB ok
2 Correct 167 ms 492396 KB ok
3 Correct 161 ms 492456 KB ok
4 Correct 164 ms 492372 KB ok
5 Correct 200 ms 492396 KB ok
6 Correct 182 ms 492436 KB ok
7 Correct 197 ms 492408 KB ok
8 Correct 183 ms 492560 KB ok
9 Correct 192 ms 495656 KB ok
10 Runtime error 885 ms 1071292 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -