oj.uz

Submission #839763

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

            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:68:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |             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:68:88: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |             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 191 ms 492516 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 492472 KB ok
2 Correct 191 ms 492364 KB ok
3 Correct 183 ms 492420 KB ok
4 Correct 195 ms 492404 KB ok
5 Correct 185 ms 492376 KB ok
6 Correct 178 ms 492364 KB ok
7 Correct 167 ms 492876 KB ok
8 Correct 183 ms 497512 KB ok
9 Runtime error 865 ms 1068612 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 182 ms 492472 KB ok
2 Correct 191 ms 492364 KB ok
3 Correct 165 ms 492396 KB ok
4 Correct 177 ms 492392 KB ok
5 Correct 204 ms 492364 KB ok
6 Correct 194 ms 492444 KB ok
7 Correct 164 ms 492356 KB ok
8 Correct 201 ms 492444 KB ok
9 Correct 188 ms 492444 KB ok
10 Correct 197 ms 492372 KB ok
11 Correct 191 ms 492372 KB ok
12 Correct 196 ms 492356 KB ok
13 Correct 170 ms 492476 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 492516 KB ok
2 Correct 182 ms 492472 KB ok
3 Correct 191 ms 492364 KB ok
4 Correct 165 ms 492396 KB ok
5 Correct 177 ms 492392 KB ok
6 Correct 204 ms 492364 KB ok
7 Correct 194 ms 492444 KB ok
8 Correct 164 ms 492356 KB ok
9 Correct 201 ms 492444 KB ok
10 Correct 188 ms 492444 KB ok
11 Correct 197 ms 492372 KB ok
12 Correct 191 ms 492372 KB ok
13 Correct 196 ms 492356 KB ok
14 Correct 170 ms 492476 KB ok
15 Correct 158 ms 492376 KB ok
16 Correct 169 ms 492492 KB ok
17 Correct 155 ms 492428 KB ok
18 Correct 202 ms 492440 KB ok
19 Correct 165 ms 492480 KB ok
20 Correct 161 ms 492492 KB ok
21 Correct 154 ms 492424 KB ok
22 Correct 166 ms 492488 KB ok
23 Correct 160 ms 492440 KB ok
24 Correct 196 ms 492452 KB ok
25 Correct 216 ms 492448 KB ok
26 Correct 195 ms 492492 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 492516 KB ok
2 Correct 182 ms 492472 KB ok
3 Correct 191 ms 492364 KB ok
4 Correct 183 ms 492420 KB ok
5 Correct 195 ms 492404 KB ok
6 Correct 165 ms 492396 KB ok
7 Correct 177 ms 492392 KB ok
8 Correct 204 ms 492364 KB ok
9 Correct 194 ms 492444 KB ok
10 Correct 164 ms 492356 KB ok
11 Correct 201 ms 492444 KB ok
12 Correct 188 ms 492444 KB ok
13 Correct 197 ms 492372 KB ok
14 Correct 191 ms 492372 KB ok
15 Correct 196 ms 492356 KB ok
16 Correct 170 ms 492476 KB ok
17 Correct 158 ms 492376 KB ok
18 Correct 169 ms 492492 KB ok
19 Correct 155 ms 492428 KB ok
20 Correct 202 ms 492440 KB ok
21 Correct 165 ms 492480 KB ok
22 Correct 161 ms 492492 KB ok
23 Correct 154 ms 492424 KB ok
24 Correct 166 ms 492488 KB ok
25 Correct 160 ms 492440 KB ok
26 Correct 196 ms 492452 KB ok
27 Correct 216 ms 492448 KB ok
28 Correct 195 ms 492492 KB ok
29 Correct 190 ms 492456 KB ok
30 Correct 181 ms 492584 KB ok
31 Correct 198 ms 492572 KB ok
32 Correct 180 ms 492492 KB ok
33 Correct 189 ms 492560 KB ok
34 Correct 193 ms 492576 KB ok
35 Correct 191 ms 492508 KB ok
36 Correct 187 ms 492576 KB ok
37 Correct 177 ms 492568 KB ok
38 Correct 193 ms 492548 KB ok
39 Correct 190 ms 492468 KB ok
40 Correct 201 ms 492472 KB ok
41 Correct 190 ms 492488 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 492516 KB ok
2 Correct 182 ms 492472 KB ok
3 Correct 191 ms 492364 KB ok
4 Correct 183 ms 492420 KB ok
5 Correct 195 ms 492404 KB ok
6 Correct 165 ms 492396 KB ok
7 Correct 177 ms 492392 KB ok
8 Correct 204 ms 492364 KB ok
9 Correct 194 ms 492444 KB ok
10 Correct 164 ms 492356 KB ok
11 Correct 201 ms 492444 KB ok
12 Correct 188 ms 492444 KB ok
13 Correct 197 ms 492372 KB ok
14 Correct 191 ms 492372 KB ok
15 Correct 196 ms 492356 KB ok
16 Correct 170 ms 492476 KB ok
17 Correct 158 ms 492376 KB ok
18 Correct 169 ms 492492 KB ok
19 Correct 155 ms 492428 KB ok
20 Correct 202 ms 492440 KB ok
21 Correct 165 ms 492480 KB ok
22 Correct 161 ms 492492 KB ok
23 Correct 154 ms 492424 KB ok
24 Correct 166 ms 492488 KB ok
25 Correct 160 ms 492440 KB ok
26 Correct 196 ms 492452 KB ok
27 Correct 216 ms 492448 KB ok
28 Correct 195 ms 492492 KB ok
29 Correct 190 ms 492456 KB ok
30 Correct 181 ms 492584 KB ok
31 Correct 198 ms 492572 KB ok
32 Correct 180 ms 492492 KB ok
33 Correct 189 ms 492560 KB ok
34 Correct 193 ms 492576 KB ok
35 Correct 191 ms 492508 KB ok
36 Correct 187 ms 492576 KB ok
37 Correct 177 ms 492568 KB ok
38 Correct 193 ms 492548 KB ok
39 Correct 190 ms 492468 KB ok
40 Correct 201 ms 492472 KB ok
41 Correct 190 ms 492488 KB ok
42 Correct 778 ms 497404 KB ok
43 Correct 682 ms 497412 KB ok
44 Correct 1562 ms 497408 KB ok
45 Correct 1959 ms 497408 KB ok
46 Correct 942 ms 497408 KB ok
47 Correct 251 ms 497308 KB ok
48 Correct 923 ms 497344 KB ok
49 Correct 1018 ms 497412 KB ok
50 Correct 630 ms 497404 KB ok
51 Correct 896 ms 497420 KB ok
52 Correct 898 ms 497412 KB ok
53 Correct 635 ms 497404 KB ok
54 Correct 1004 ms 497412 KB ok
55 Correct 1103 ms 497408 KB ok
56 Correct 525 ms 497312 KB ok
57 Execution timed out 4639 ms 497452 KB Time limit exceeded
58 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 492516 KB ok
2 Correct 182 ms 492472 KB ok
3 Correct 191 ms 492364 KB ok
4 Correct 183 ms 492420 KB ok
5 Correct 195 ms 492404 KB ok
6 Correct 185 ms 492376 KB ok
7 Correct 178 ms 492364 KB ok
8 Correct 167 ms 492876 KB ok
9 Correct 183 ms 497512 KB ok
10 Runtime error 865 ms 1068612 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -