oj.uz

Submission #987094

# Submission time Handle Problem Language Result Execution time Memory
987094 2024-05-21T20:51:30 Z activedeltorre Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 498000 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];

pii tmp[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; L <= r; ++L)
    {
        int Li = li;
        int Ri = ri;
        for (int R = r; R >= L; --R)
        {
            if (L == l && R == r)
            {
                continue;
            }
            while (Li >= 0 && query(Li, L, i - 1, R) == 0)
                Li--;
            while (Ri < N && query(i, L, Ri, R) == 0)
                Ri++;
            tmp[L][R] = pii{Li, Ri};
            res = max(res, calc(i, L, R) + (R - L + 1) * (li - Li + Ri - ri));
        }
    }
    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 271 ms 494164 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 494164 KB ok
2 Correct 224 ms 494280 KB ok
3 Correct 176 ms 494416 KB ok
4 Correct 201 ms 494420 KB ok
5 Correct 164 ms 494172 KB ok
6 Correct 202 ms 494188 KB ok
7 Correct 341 ms 494704 KB ok
8 Execution timed out 4538 ms 498000 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 494164 KB ok
2 Correct 224 ms 494280 KB ok
3 Correct 186 ms 494568 KB ok
4 Correct 166 ms 494164 KB ok
5 Correct 197 ms 494164 KB ok
6 Correct 188 ms 494224 KB ok
7 Correct 197 ms 494164 KB ok
8 Correct 198 ms 494360 KB ok
9 Correct 192 ms 494252 KB ok
10 Correct 195 ms 494396 KB ok
11 Correct 209 ms 494208 KB ok
12 Correct 198 ms 494324 KB ok
13 Correct 197 ms 494252 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 494164 KB ok
2 Correct 208 ms 494164 KB ok
3 Correct 224 ms 494280 KB ok
4 Correct 186 ms 494568 KB ok
5 Correct 166 ms 494164 KB ok
6 Correct 197 ms 494164 KB ok
7 Correct 188 ms 494224 KB ok
8 Correct 197 ms 494164 KB ok
9 Correct 198 ms 494360 KB ok
10 Correct 192 ms 494252 KB ok
11 Correct 195 ms 494396 KB ok
12 Correct 209 ms 494208 KB ok
13 Correct 198 ms 494324 KB ok
14 Correct 197 ms 494252 KB ok
15 Correct 197 ms 494372 KB ok
16 Correct 197 ms 494280 KB ok
17 Correct 207 ms 494356 KB ok
18 Correct 165 ms 494160 KB ok
19 Correct 204 ms 494452 KB ok
20 Correct 196 ms 494416 KB ok
21 Correct 172 ms 494372 KB ok
22 Correct 192 ms 494160 KB ok
23 Correct 195 ms 494336 KB ok
24 Correct 201 ms 494420 KB ok
25 Correct 196 ms 494300 KB ok
26 Correct 194 ms 494360 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 494164 KB ok
2 Correct 208 ms 494164 KB ok
3 Correct 224 ms 494280 KB ok
4 Correct 176 ms 494416 KB ok
5 Correct 201 ms 494420 KB ok
6 Correct 186 ms 494568 KB ok
7 Correct 166 ms 494164 KB ok
8 Correct 197 ms 494164 KB ok
9 Correct 188 ms 494224 KB ok
10 Correct 197 ms 494164 KB ok
11 Correct 198 ms 494360 KB ok
12 Correct 192 ms 494252 KB ok
13 Correct 195 ms 494396 KB ok
14 Correct 209 ms 494208 KB ok
15 Correct 198 ms 494324 KB ok
16 Correct 197 ms 494252 KB ok
17 Correct 197 ms 494372 KB ok
18 Correct 197 ms 494280 KB ok
19 Correct 207 ms 494356 KB ok
20 Correct 165 ms 494160 KB ok
21 Correct 204 ms 494452 KB ok
22 Correct 196 ms 494416 KB ok
23 Correct 172 ms 494372 KB ok
24 Correct 192 ms 494160 KB ok
25 Correct 195 ms 494336 KB ok
26 Correct 201 ms 494420 KB ok
27 Correct 196 ms 494300 KB ok
28 Correct 194 ms 494360 KB ok
29 Correct 199 ms 494344 KB ok
30 Correct 191 ms 494360 KB ok
31 Correct 215 ms 494416 KB ok
32 Correct 180 ms 494336 KB ok
33 Correct 179 ms 494416 KB ok
34 Correct 210 ms 494420 KB ok
35 Correct 215 ms 494508 KB ok
36 Correct 207 ms 494420 KB ok
37 Correct 215 ms 494504 KB ok
38 Correct 208 ms 494420 KB ok
39 Correct 219 ms 494344 KB ok
40 Correct 202 ms 494416 KB ok
41 Correct 232 ms 494376 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 494164 KB ok
2 Correct 208 ms 494164 KB ok
3 Correct 224 ms 494280 KB ok
4 Correct 176 ms 494416 KB ok
5 Correct 201 ms 494420 KB ok
6 Correct 186 ms 494568 KB ok
7 Correct 166 ms 494164 KB ok
8 Correct 197 ms 494164 KB ok
9 Correct 188 ms 494224 KB ok
10 Correct 197 ms 494164 KB ok
11 Correct 198 ms 494360 KB ok
12 Correct 192 ms 494252 KB ok
13 Correct 195 ms 494396 KB ok
14 Correct 209 ms 494208 KB ok
15 Correct 198 ms 494324 KB ok
16 Correct 197 ms 494252 KB ok
17 Correct 197 ms 494372 KB ok
18 Correct 197 ms 494280 KB ok
19 Correct 207 ms 494356 KB ok
20 Correct 165 ms 494160 KB ok
21 Correct 204 ms 494452 KB ok
22 Correct 196 ms 494416 KB ok
23 Correct 172 ms 494372 KB ok
24 Correct 192 ms 494160 KB ok
25 Correct 195 ms 494336 KB ok
26 Correct 201 ms 494420 KB ok
27 Correct 196 ms 494300 KB ok
28 Correct 194 ms 494360 KB ok
29 Correct 199 ms 494344 KB ok
30 Correct 191 ms 494360 KB ok
31 Correct 215 ms 494416 KB ok
32 Correct 180 ms 494336 KB ok
33 Correct 179 ms 494416 KB ok
34 Correct 210 ms 494420 KB ok
35 Correct 215 ms 494508 KB ok
36 Correct 207 ms 494420 KB ok
37 Correct 215 ms 494504 KB ok
38 Correct 208 ms 494420 KB ok
39 Correct 219 ms 494344 KB ok
40 Correct 202 ms 494416 KB ok
41 Correct 232 ms 494376 KB ok
42 Execution timed out 4564 ms 497856 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 494164 KB ok
2 Correct 208 ms 494164 KB ok
3 Correct 224 ms 494280 KB ok
4 Correct 176 ms 494416 KB ok
5 Correct 201 ms 494420 KB ok
6 Correct 164 ms 494172 KB ok
7 Correct 202 ms 494188 KB ok
8 Correct 341 ms 494704 KB ok
9 Execution timed out 4538 ms 498000 KB Time limit exceeded
10 Halted 0 ms 0 KB -