oj.uz

Submission #839772

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

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 make_pair(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++;
            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 172 ms 492392 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 492348 KB ok
2 Correct 183 ms 492428 KB ok
3 Correct 198 ms 492404 KB ok
4 Correct 182 ms 492404 KB ok
5 Correct 171 ms 492348 KB ok
6 Correct 176 ms 492400 KB ok
7 Correct 2281 ms 492604 KB ok
8 Execution timed out 4609 ms 495756 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 492348 KB ok
2 Correct 183 ms 492428 KB ok
3 Correct 184 ms 492348 KB ok
4 Correct 221 ms 492376 KB ok
5 Correct 172 ms 492364 KB ok
6 Correct 186 ms 492384 KB ok
7 Correct 177 ms 492356 KB ok
8 Correct 147 ms 492416 KB ok
9 Correct 192 ms 492440 KB ok
10 Correct 165 ms 492388 KB ok
11 Correct 191 ms 492352 KB ok
12 Correct 178 ms 492392 KB ok
13 Correct 161 ms 492428 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492392 KB ok
2 Correct 179 ms 492348 KB ok
3 Correct 183 ms 492428 KB ok
4 Correct 184 ms 492348 KB ok
5 Correct 221 ms 492376 KB ok
6 Correct 172 ms 492364 KB ok
7 Correct 186 ms 492384 KB ok
8 Correct 177 ms 492356 KB ok
9 Correct 147 ms 492416 KB ok
10 Correct 192 ms 492440 KB ok
11 Correct 165 ms 492388 KB ok
12 Correct 191 ms 492352 KB ok
13 Correct 178 ms 492392 KB ok
14 Correct 161 ms 492428 KB ok
15 Correct 219 ms 492444 KB ok
16 Correct 162 ms 492352 KB ok
17 Correct 192 ms 492440 KB ok
18 Correct 204 ms 492456 KB ok
19 Correct 174 ms 492436 KB ok
20 Correct 291 ms 492380 KB ok
21 Correct 179 ms 492340 KB ok
22 Correct 174 ms 492360 KB ok
23 Correct 176 ms 492368 KB ok
24 Correct 246 ms 492472 KB ok
25 Correct 190 ms 492432 KB ok
26 Correct 201 ms 492348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492392 KB ok
2 Correct 179 ms 492348 KB ok
3 Correct 183 ms 492428 KB ok
4 Correct 198 ms 492404 KB ok
5 Correct 182 ms 492404 KB ok
6 Correct 184 ms 492348 KB ok
7 Correct 221 ms 492376 KB ok
8 Correct 172 ms 492364 KB ok
9 Correct 186 ms 492384 KB ok
10 Correct 177 ms 492356 KB ok
11 Correct 147 ms 492416 KB ok
12 Correct 192 ms 492440 KB ok
13 Correct 165 ms 492388 KB ok
14 Correct 191 ms 492352 KB ok
15 Correct 178 ms 492392 KB ok
16 Correct 161 ms 492428 KB ok
17 Correct 219 ms 492444 KB ok
18 Correct 162 ms 492352 KB ok
19 Correct 192 ms 492440 KB ok
20 Correct 204 ms 492456 KB ok
21 Correct 174 ms 492436 KB ok
22 Correct 291 ms 492380 KB ok
23 Correct 179 ms 492340 KB ok
24 Correct 174 ms 492360 KB ok
25 Correct 176 ms 492368 KB ok
26 Correct 246 ms 492472 KB ok
27 Correct 190 ms 492432 KB ok
28 Correct 201 ms 492348 KB ok
29 Correct 187 ms 492516 KB ok
30 Correct 193 ms 492396 KB ok
31 Correct 334 ms 492424 KB ok
32 Correct 175 ms 492404 KB ok
33 Correct 208 ms 492380 KB ok
34 Correct 185 ms 492544 KB ok
35 Correct 175 ms 492400 KB ok
36 Correct 173 ms 492444 KB ok
37 Correct 310 ms 492380 KB ok
38 Correct 174 ms 492384 KB ok
39 Correct 171 ms 492472 KB ok
40 Correct 184 ms 492456 KB ok
41 Correct 166 ms 492472 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492392 KB ok
2 Correct 179 ms 492348 KB ok
3 Correct 183 ms 492428 KB ok
4 Correct 198 ms 492404 KB ok
5 Correct 182 ms 492404 KB ok
6 Correct 184 ms 492348 KB ok
7 Correct 221 ms 492376 KB ok
8 Correct 172 ms 492364 KB ok
9 Correct 186 ms 492384 KB ok
10 Correct 177 ms 492356 KB ok
11 Correct 147 ms 492416 KB ok
12 Correct 192 ms 492440 KB ok
13 Correct 165 ms 492388 KB ok
14 Correct 191 ms 492352 KB ok
15 Correct 178 ms 492392 KB ok
16 Correct 161 ms 492428 KB ok
17 Correct 219 ms 492444 KB ok
18 Correct 162 ms 492352 KB ok
19 Correct 192 ms 492440 KB ok
20 Correct 204 ms 492456 KB ok
21 Correct 174 ms 492436 KB ok
22 Correct 291 ms 492380 KB ok
23 Correct 179 ms 492340 KB ok
24 Correct 174 ms 492360 KB ok
25 Correct 176 ms 492368 KB ok
26 Correct 246 ms 492472 KB ok
27 Correct 190 ms 492432 KB ok
28 Correct 201 ms 492348 KB ok
29 Correct 187 ms 492516 KB ok
30 Correct 193 ms 492396 KB ok
31 Correct 334 ms 492424 KB ok
32 Correct 175 ms 492404 KB ok
33 Correct 208 ms 492380 KB ok
34 Correct 185 ms 492544 KB ok
35 Correct 175 ms 492400 KB ok
36 Correct 173 ms 492444 KB ok
37 Correct 310 ms 492380 KB ok
38 Correct 174 ms 492384 KB ok
39 Correct 171 ms 492472 KB ok
40 Correct 184 ms 492456 KB ok
41 Correct 166 ms 492472 KB ok
42 Execution timed out 4537 ms 495844 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 492392 KB ok
2 Correct 179 ms 492348 KB ok
3 Correct 183 ms 492428 KB ok
4 Correct 198 ms 492404 KB ok
5 Correct 182 ms 492404 KB ok
6 Correct 171 ms 492348 KB ok
7 Correct 176 ms 492400 KB ok
8 Correct 2281 ms 492604 KB ok
9 Execution timed out 4609 ms 495756 KB Time limit exceeded
10 Halted 0 ms 0 KB -