oj.uz

Submission #839764

# Submission time Handle Problem Language Result Execution time Memory
839764 2023-08-30T15:50:34 Z model_code Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 541604 KB 
// correct/sol_db_N5_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 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);
    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};

            if (Li == li && Ri == ri || L > l && tmp[L - 1][R] == pii{Li, Ri} || R < r && tmp[L][R + 1] == pii{Li, Ri})
            {
                continue;
            }
            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;
}

Compilation message

soccer.cpp: In function 'int calc(int, int, int)':
soccer.cpp:64:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   64 |             if (Li == li && Ri == ri || L > l && tmp[L - 1][R] == pii{Li, Ri} || R < r && tmp[L][R + 1] == pii{Li, Ri})
      |                 ~~~~~~~~~^~~~~~~~~~~
soccer.cpp:64:88: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   64 |             if (Li == li && Ri == ri || L > l && tmp[L - 1][R] == pii{Li, Ri} || R < r && tmp[L][R + 1] == pii{Li, Ri})
      |                                                                                  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 492432 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 492460 KB ok
2 Correct 186 ms 492476 KB ok
3 Correct 187 ms 492384 KB ok
4 Correct 192 ms 492492 KB ok
5 Correct 185 ms 492452 KB ok
6 Correct 160 ms 492364 KB ok
7 Correct 213 ms 492892 KB ok
8 Correct 517 ms 497404 KB ok
9 Execution timed out 4532 ms 541604 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 492460 KB ok
2 Correct 186 ms 492476 KB ok
3 Correct 190 ms 492376 KB ok
4 Correct 198 ms 492380 KB ok
5 Correct 221 ms 492492 KB ok
6 Correct 155 ms 492364 KB ok
7 Correct 201 ms 492432 KB ok
8 Correct 194 ms 492404 KB ok
9 Correct 170 ms 492364 KB ok
10 Correct 155 ms 492400 KB ok
11 Correct 191 ms 492416 KB ok
12 Correct 192 ms 492472 KB ok
13 Correct 212 ms 492400 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 492432 KB ok
2 Correct 201 ms 492460 KB ok
3 Correct 186 ms 492476 KB ok
4 Correct 190 ms 492376 KB ok
5 Correct 198 ms 492380 KB ok
6 Correct 221 ms 492492 KB ok
7 Correct 155 ms 492364 KB ok
8 Correct 201 ms 492432 KB ok
9 Correct 194 ms 492404 KB ok
10 Correct 170 ms 492364 KB ok
11 Correct 155 ms 492400 KB ok
12 Correct 191 ms 492416 KB ok
13 Correct 192 ms 492472 KB ok
14 Correct 212 ms 492400 KB ok
15 Correct 150 ms 492476 KB ok
16 Correct 169 ms 492452 KB ok
17 Correct 185 ms 492520 KB ok
18 Correct 171 ms 492428 KB ok
19 Correct 203 ms 492376 KB ok
20 Correct 175 ms 492496 KB ok
21 Correct 207 ms 492448 KB ok
22 Correct 203 ms 492372 KB ok
23 Correct 177 ms 492484 KB ok
24 Correct 186 ms 492432 KB ok
25 Correct 219 ms 492388 KB ok
26 Correct 211 ms 492488 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 492432 KB ok
2 Correct 201 ms 492460 KB ok
3 Correct 186 ms 492476 KB ok
4 Correct 187 ms 492384 KB ok
5 Correct 192 ms 492492 KB ok
6 Correct 190 ms 492376 KB ok
7 Correct 198 ms 492380 KB ok
8 Correct 221 ms 492492 KB ok
9 Correct 155 ms 492364 KB ok
10 Correct 201 ms 492432 KB ok
11 Correct 194 ms 492404 KB ok
12 Correct 170 ms 492364 KB ok
13 Correct 155 ms 492400 KB ok
14 Correct 191 ms 492416 KB ok
15 Correct 192 ms 492472 KB ok
16 Correct 212 ms 492400 KB ok
17 Correct 150 ms 492476 KB ok
18 Correct 169 ms 492452 KB ok
19 Correct 185 ms 492520 KB ok
20 Correct 171 ms 492428 KB ok
21 Correct 203 ms 492376 KB ok
22 Correct 175 ms 492496 KB ok
23 Correct 207 ms 492448 KB ok
24 Correct 203 ms 492372 KB ok
25 Correct 177 ms 492484 KB ok
26 Correct 186 ms 492432 KB ok
27 Correct 219 ms 492388 KB ok
28 Correct 211 ms 492488 KB ok
29 Correct 174 ms 492400 KB ok
30 Correct 191 ms 492516 KB ok
31 Correct 189 ms 492556 KB ok
32 Correct 152 ms 492556 KB ok
33 Correct 172 ms 492508 KB ok
34 Correct 158 ms 492572 KB ok
35 Correct 148 ms 492576 KB ok
36 Correct 170 ms 492468 KB ok
37 Correct 143 ms 492556 KB ok
38 Correct 175 ms 492536 KB ok
39 Correct 147 ms 492492 KB ok
40 Correct 185 ms 492548 KB ok
41 Correct 182 ms 492572 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 492432 KB ok
2 Correct 201 ms 492460 KB ok
3 Correct 186 ms 492476 KB ok
4 Correct 187 ms 492384 KB ok
5 Correct 192 ms 492492 KB ok
6 Correct 190 ms 492376 KB ok
7 Correct 198 ms 492380 KB ok
8 Correct 221 ms 492492 KB ok
9 Correct 155 ms 492364 KB ok
10 Correct 201 ms 492432 KB ok
11 Correct 194 ms 492404 KB ok
12 Correct 170 ms 492364 KB ok
13 Correct 155 ms 492400 KB ok
14 Correct 191 ms 492416 KB ok
15 Correct 192 ms 492472 KB ok
16 Correct 212 ms 492400 KB ok
17 Correct 150 ms 492476 KB ok
18 Correct 169 ms 492452 KB ok
19 Correct 185 ms 492520 KB ok
20 Correct 171 ms 492428 KB ok
21 Correct 203 ms 492376 KB ok
22 Correct 175 ms 492496 KB ok
23 Correct 207 ms 492448 KB ok
24 Correct 203 ms 492372 KB ok
25 Correct 177 ms 492484 KB ok
26 Correct 186 ms 492432 KB ok
27 Correct 219 ms 492388 KB ok
28 Correct 211 ms 492488 KB ok
29 Correct 174 ms 492400 KB ok
30 Correct 191 ms 492516 KB ok
31 Correct 189 ms 492556 KB ok
32 Correct 152 ms 492556 KB ok
33 Correct 172 ms 492508 KB ok
34 Correct 158 ms 492572 KB ok
35 Correct 148 ms 492576 KB ok
36 Correct 170 ms 492468 KB ok
37 Correct 143 ms 492556 KB ok
38 Correct 175 ms 492536 KB ok
39 Correct 147 ms 492492 KB ok
40 Correct 185 ms 492548 KB ok
41 Correct 182 ms 492572 KB ok
42 Correct 1047 ms 497404 KB ok
43 Correct 793 ms 497408 KB ok
44 Correct 3616 ms 497416 KB ok
45 Execution timed out 4537 ms 497292 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 492432 KB ok
2 Correct 201 ms 492460 KB ok
3 Correct 186 ms 492476 KB ok
4 Correct 187 ms 492384 KB ok
5 Correct 192 ms 492492 KB ok
6 Correct 185 ms 492452 KB ok
7 Correct 160 ms 492364 KB ok
8 Correct 213 ms 492892 KB ok
9 Correct 517 ms 497404 KB ok
10 Execution timed out 4532 ms 541604 KB Time limit exceeded
11 Halted 0 ms 0 KB -