oj.uz

Submission #987098

# Submission time Handle Problem Language Result Execution time Memory
987098 2024-05-21T21:07:56 Z activedeltorre Soccer Stadium (IOI23_soccer) C++17
64 / 100
 1041 ms 1074180 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 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 240 ms 492484 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 492368 KB ok
2 Correct 178 ms 492592 KB ok
3 Correct 178 ms 492504 KB ok
4 Correct 178 ms 492520 KB ok
5 Correct 175 ms 492372 KB ok
6 Correct 179 ms 492372 KB ok
7 Correct 177 ms 492672 KB ok
8 Correct 191 ms 496168 KB ok
9 Runtime error 1041 ms 1074180 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 181 ms 492368 KB ok
2 Correct 178 ms 492592 KB ok
3 Correct 282 ms 492372 KB ok
4 Correct 184 ms 492368 KB ok
5 Correct 162 ms 492368 KB ok
6 Correct 189 ms 492372 KB ok
7 Correct 183 ms 492364 KB ok
8 Correct 184 ms 492472 KB ok
9 Correct 183 ms 492372 KB ok
10 Correct 197 ms 492372 KB ok
11 Correct 156 ms 492476 KB ok
12 Correct 184 ms 492468 KB ok
13 Correct 186 ms 492540 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 492484 KB ok
2 Correct 181 ms 492368 KB ok
3 Correct 178 ms 492592 KB ok
4 Correct 282 ms 492372 KB ok
5 Correct 184 ms 492368 KB ok
6 Correct 162 ms 492368 KB ok
7 Correct 189 ms 492372 KB ok
8 Correct 183 ms 492364 KB ok
9 Correct 184 ms 492472 KB ok
10 Correct 183 ms 492372 KB ok
11 Correct 197 ms 492372 KB ok
12 Correct 156 ms 492476 KB ok
13 Correct 184 ms 492468 KB ok
14 Correct 186 ms 492540 KB ok
15 Correct 185 ms 492532 KB ok
16 Correct 179 ms 492576 KB ok
17 Correct 185 ms 492368 KB ok
18 Correct 157 ms 492444 KB ok
19 Correct 190 ms 492372 KB ok
20 Correct 156 ms 492560 KB ok
21 Correct 187 ms 492432 KB ok
22 Correct 165 ms 492468 KB ok
23 Correct 186 ms 492344 KB ok
24 Correct 185 ms 492388 KB ok
25 Correct 188 ms 492368 KB ok
26 Correct 187 ms 492372 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 492484 KB ok
2 Correct 181 ms 492368 KB ok
3 Correct 178 ms 492592 KB ok
4 Correct 178 ms 492504 KB ok
5 Correct 178 ms 492520 KB ok
6 Correct 282 ms 492372 KB ok
7 Correct 184 ms 492368 KB ok
8 Correct 162 ms 492368 KB ok
9 Correct 189 ms 492372 KB ok
10 Correct 183 ms 492364 KB ok
11 Correct 184 ms 492472 KB ok
12 Correct 183 ms 492372 KB ok
13 Correct 197 ms 492372 KB ok
14 Correct 156 ms 492476 KB ok
15 Correct 184 ms 492468 KB ok
16 Correct 186 ms 492540 KB ok
17 Correct 185 ms 492532 KB ok
18 Correct 179 ms 492576 KB ok
19 Correct 185 ms 492368 KB ok
20 Correct 157 ms 492444 KB ok
21 Correct 190 ms 492372 KB ok
22 Correct 156 ms 492560 KB ok
23 Correct 187 ms 492432 KB ok
24 Correct 165 ms 492468 KB ok
25 Correct 186 ms 492344 KB ok
26 Correct 185 ms 492388 KB ok
27 Correct 188 ms 492368 KB ok
28 Correct 187 ms 492372 KB ok
29 Correct 187 ms 492368 KB ok
30 Correct 189 ms 492548 KB ok
31 Correct 185 ms 492504 KB ok
32 Correct 185 ms 492368 KB ok
33 Correct 195 ms 492504 KB ok
34 Correct 184 ms 492372 KB ok
35 Correct 186 ms 492536 KB ok
36 Correct 177 ms 492348 KB ok
37 Correct 185 ms 492368 KB ok
38 Correct 181 ms 492476 KB ok
39 Correct 188 ms 492480 KB ok
40 Correct 176 ms 492564 KB ok
41 Correct 184 ms 492536 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 492484 KB ok
2 Correct 181 ms 492368 KB ok
3 Correct 178 ms 492592 KB ok
4 Correct 178 ms 492504 KB ok
5 Correct 178 ms 492520 KB ok
6 Correct 282 ms 492372 KB ok
7 Correct 184 ms 492368 KB ok
8 Correct 162 ms 492368 KB ok
9 Correct 189 ms 492372 KB ok
10 Correct 183 ms 492364 KB ok
11 Correct 184 ms 492472 KB ok
12 Correct 183 ms 492372 KB ok
13 Correct 197 ms 492372 KB ok
14 Correct 156 ms 492476 KB ok
15 Correct 184 ms 492468 KB ok
16 Correct 186 ms 492540 KB ok
17 Correct 185 ms 492532 KB ok
18 Correct 179 ms 492576 KB ok
19 Correct 185 ms 492368 KB ok
20 Correct 157 ms 492444 KB ok
21 Correct 190 ms 492372 KB ok
22 Correct 156 ms 492560 KB ok
23 Correct 187 ms 492432 KB ok
24 Correct 165 ms 492468 KB ok
25 Correct 186 ms 492344 KB ok
26 Correct 185 ms 492388 KB ok
27 Correct 188 ms 492368 KB ok
28 Correct 187 ms 492372 KB ok
29 Correct 187 ms 492368 KB ok
30 Correct 189 ms 492548 KB ok
31 Correct 185 ms 492504 KB ok
32 Correct 185 ms 492368 KB ok
33 Correct 195 ms 492504 KB ok
34 Correct 184 ms 492372 KB ok
35 Correct 186 ms 492536 KB ok
36 Correct 177 ms 492348 KB ok
37 Correct 185 ms 492368 KB ok
38 Correct 181 ms 492476 KB ok
39 Correct 188 ms 492480 KB ok
40 Correct 176 ms 492564 KB ok
41 Correct 184 ms 492536 KB ok
42 Correct 216 ms 496072 KB ok
43 Correct 247 ms 495908 KB ok
44 Correct 194 ms 495956 KB ok
45 Correct 214 ms 495952 KB ok
46 Correct 230 ms 495952 KB ok
47 Correct 199 ms 496192 KB ok
48 Correct 204 ms 496008 KB ok
49 Correct 180 ms 496040 KB ok
50 Correct 365 ms 496384 KB ok
51 Correct 212 ms 496068 KB ok
52 Correct 204 ms 496200 KB ok
53 Correct 202 ms 495952 KB ok
54 Correct 203 ms 496064 KB ok
55 Correct 204 ms 495952 KB ok
56 Correct 204 ms 495956 KB ok
57 Correct 341 ms 495956 KB ok
58 Correct 343 ms 495956 KB ok
59 Correct 338 ms 496096 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 492484 KB ok
2 Correct 181 ms 492368 KB ok
3 Correct 178 ms 492592 KB ok
4 Correct 178 ms 492504 KB ok
5 Correct 178 ms 492520 KB ok
6 Correct 175 ms 492372 KB ok
7 Correct 179 ms 492372 KB ok
8 Correct 177 ms 492672 KB ok
9 Correct 191 ms 496168 KB ok
10 Runtime error 1041 ms 1074180 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -