oj.uz

Submission #987095

# Submission time Handle Problem Language Result Execution time Memory
987095 2024-05-21T20:52:22 Z activedeltorre Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1068812 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};

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 494172 KB ok
2 Correct 185 ms 494204 KB ok
3 Correct 179 ms 494404 KB ok
4 Correct 180 ms 494416 KB ok
5 Correct 186 ms 494548 KB ok
6 Correct 165 ms 494204 KB ok
7 Correct 166 ms 494592 KB ok
8 Correct 176 ms 497308 KB ok
9 Runtime error 1016 ms 1068812 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 168 ms 494172 KB ok
2 Correct 185 ms 494204 KB ok
3 Correct 191 ms 494260 KB ok
4 Correct 174 ms 494244 KB ok
5 Correct 211 ms 494388 KB ok
6 Correct 234 ms 494152 KB ok
7 Correct 212 ms 494580 KB ok
8 Correct 178 ms 494188 KB ok
9 Correct 221 ms 494356 KB ok
10 Correct 180 ms 494304 KB ok
11 Correct 233 ms 494172 KB ok
12 Correct 185 ms 494164 KB ok
13 Correct 213 ms 494148 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 494160 KB ok
2 Correct 168 ms 494172 KB ok
3 Correct 185 ms 494204 KB ok
4 Correct 191 ms 494260 KB ok
5 Correct 174 ms 494244 KB ok
6 Correct 211 ms 494388 KB ok
7 Correct 234 ms 494152 KB ok
8 Correct 212 ms 494580 KB ok
9 Correct 178 ms 494188 KB ok
10 Correct 221 ms 494356 KB ok
11 Correct 180 ms 494304 KB ok
12 Correct 233 ms 494172 KB ok
13 Correct 185 ms 494164 KB ok
14 Correct 213 ms 494148 KB ok
15 Correct 214 ms 494240 KB ok
16 Correct 175 ms 494416 KB ok
17 Correct 210 ms 494208 KB ok
18 Correct 214 ms 494192 KB ok
19 Correct 196 ms 494676 KB ok
20 Correct 212 ms 494248 KB ok
21 Correct 212 ms 494416 KB ok
22 Correct 217 ms 494236 KB ok
23 Correct 213 ms 494412 KB ok
24 Correct 221 ms 494164 KB ok
25 Correct 173 ms 494416 KB ok
26 Correct 215 ms 494164 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 494160 KB ok
2 Correct 168 ms 494172 KB ok
3 Correct 185 ms 494204 KB ok
4 Correct 179 ms 494404 KB ok
5 Correct 180 ms 494416 KB ok
6 Correct 191 ms 494260 KB ok
7 Correct 174 ms 494244 KB ok
8 Correct 211 ms 494388 KB ok
9 Correct 234 ms 494152 KB ok
10 Correct 212 ms 494580 KB ok
11 Correct 178 ms 494188 KB ok
12 Correct 221 ms 494356 KB ok
13 Correct 180 ms 494304 KB ok
14 Correct 233 ms 494172 KB ok
15 Correct 185 ms 494164 KB ok
16 Correct 213 ms 494148 KB ok
17 Correct 214 ms 494240 KB ok
18 Correct 175 ms 494416 KB ok
19 Correct 210 ms 494208 KB ok
20 Correct 214 ms 494192 KB ok
21 Correct 196 ms 494676 KB ok
22 Correct 212 ms 494248 KB ok
23 Correct 212 ms 494416 KB ok
24 Correct 217 ms 494236 KB ok
25 Correct 213 ms 494412 KB ok
26 Correct 221 ms 494164 KB ok
27 Correct 173 ms 494416 KB ok
28 Correct 215 ms 494164 KB ok
29 Correct 215 ms 494168 KB ok
30 Correct 206 ms 494372 KB ok
31 Correct 214 ms 494276 KB ok
32 Correct 202 ms 494484 KB ok
33 Correct 222 ms 494336 KB ok
34 Correct 165 ms 494416 KB ok
35 Correct 167 ms 494420 KB ok
36 Correct 169 ms 494420 KB ok
37 Correct 200 ms 494468 KB ok
38 Correct 197 ms 494512 KB ok
39 Correct 199 ms 494420 KB ok
40 Correct 209 ms 494496 KB ok
41 Correct 205 ms 494368 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 494160 KB ok
2 Correct 168 ms 494172 KB ok
3 Correct 185 ms 494204 KB ok
4 Correct 179 ms 494404 KB ok
5 Correct 180 ms 494416 KB ok
6 Correct 191 ms 494260 KB ok
7 Correct 174 ms 494244 KB ok
8 Correct 211 ms 494388 KB ok
9 Correct 234 ms 494152 KB ok
10 Correct 212 ms 494580 KB ok
11 Correct 178 ms 494188 KB ok
12 Correct 221 ms 494356 KB ok
13 Correct 180 ms 494304 KB ok
14 Correct 233 ms 494172 KB ok
15 Correct 185 ms 494164 KB ok
16 Correct 213 ms 494148 KB ok
17 Correct 214 ms 494240 KB ok
18 Correct 175 ms 494416 KB ok
19 Correct 210 ms 494208 KB ok
20 Correct 214 ms 494192 KB ok
21 Correct 196 ms 494676 KB ok
22 Correct 212 ms 494248 KB ok
23 Correct 212 ms 494416 KB ok
24 Correct 217 ms 494236 KB ok
25 Correct 213 ms 494412 KB ok
26 Correct 221 ms 494164 KB ok
27 Correct 173 ms 494416 KB ok
28 Correct 215 ms 494164 KB ok
29 Correct 215 ms 494168 KB ok
30 Correct 206 ms 494372 KB ok
31 Correct 214 ms 494276 KB ok
32 Correct 202 ms 494484 KB ok
33 Correct 222 ms 494336 KB ok
34 Correct 165 ms 494416 KB ok
35 Correct 167 ms 494420 KB ok
36 Correct 169 ms 494420 KB ok
37 Correct 200 ms 494468 KB ok
38 Correct 197 ms 494512 KB ok
39 Correct 199 ms 494420 KB ok
40 Correct 209 ms 494496 KB ok
41 Correct 205 ms 494368 KB ok
42 Correct 708 ms 497916 KB ok
43 Correct 689 ms 498032 KB ok
44 Correct 1502 ms 497792 KB ok
45 Correct 1885 ms 498032 KB ok
46 Correct 924 ms 498092 KB ok
47 Correct 236 ms 498036 KB ok
48 Correct 899 ms 498032 KB ok
49 Correct 935 ms 498260 KB ok
50 Correct 545 ms 498000 KB ok
51 Correct 868 ms 498000 KB ok
52 Correct 859 ms 498028 KB ok
53 Correct 566 ms 498036 KB ok
54 Correct 837 ms 497996 KB ok
55 Correct 997 ms 498260 KB ok
56 Correct 520 ms 497996 KB ok
57 Execution timed out 4549 ms 497988 KB Time limit exceeded
58 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 494160 KB ok
2 Correct 168 ms 494172 KB ok
3 Correct 185 ms 494204 KB ok
4 Correct 179 ms 494404 KB ok
5 Correct 180 ms 494416 KB ok
6 Correct 186 ms 494548 KB ok
7 Correct 165 ms 494204 KB ok
8 Correct 166 ms 494592 KB ok
9 Correct 176 ms 497308 KB ok
10 Runtime error 1016 ms 1068812 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -