oj.uz

Submission #839760

# Submission time Handle Problem Language Result Execution time Memory
839760 2023-08-30T15:50:26 Z model_code Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 495484 KB 
// correct/sol_db_N6.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) {
        for (int R = L; R <= r; ++R) {
            if (L == l && R == r) {
                continue;
            }
            int Li = li;
            int Ri = ri;
            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 171 ms 492456 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 492344 KB ok
2 Correct 147 ms 492364 KB ok
3 Correct 223 ms 492404 KB ok
4 Correct 194 ms 492352 KB ok
5 Correct 196 ms 492456 KB ok
6 Correct 201 ms 492440 KB ok
7 Execution timed out 4590 ms 492496 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 492344 KB ok
2 Correct 147 ms 492364 KB ok
3 Correct 234 ms 492460 KB ok
4 Correct 185 ms 492404 KB ok
5 Correct 199 ms 492460 KB ok
6 Correct 201 ms 492352 KB ok
7 Correct 186 ms 492444 KB ok
8 Correct 198 ms 492380 KB ok
9 Correct 221 ms 492444 KB ok
10 Correct 192 ms 492412 KB ok
11 Correct 201 ms 492460 KB ok
12 Correct 192 ms 492384 KB ok
13 Correct 195 ms 492352 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 492456 KB ok
2 Correct 149 ms 492344 KB ok
3 Correct 147 ms 492364 KB ok
4 Correct 234 ms 492460 KB ok
5 Correct 185 ms 492404 KB ok
6 Correct 199 ms 492460 KB ok
7 Correct 201 ms 492352 KB ok
8 Correct 186 ms 492444 KB ok
9 Correct 198 ms 492380 KB ok
10 Correct 221 ms 492444 KB ok
11 Correct 192 ms 492412 KB ok
12 Correct 201 ms 492460 KB ok
13 Correct 192 ms 492384 KB ok
14 Correct 195 ms 492352 KB ok
15 Correct 203 ms 492348 KB ok
16 Correct 195 ms 492376 KB ok
17 Correct 192 ms 492416 KB ok
18 Correct 197 ms 492424 KB ok
19 Correct 195 ms 492364 KB ok
20 Correct 183 ms 492400 KB ok
21 Correct 210 ms 492428 KB ok
22 Correct 194 ms 492472 KB ok
23 Correct 190 ms 492424 KB ok
24 Correct 193 ms 492448 KB ok
25 Correct 188 ms 492432 KB ok
26 Correct 218 ms 492356 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 492456 KB ok
2 Correct 149 ms 492344 KB ok
3 Correct 147 ms 492364 KB ok
4 Correct 223 ms 492404 KB ok
5 Correct 194 ms 492352 KB ok
6 Correct 234 ms 492460 KB ok
7 Correct 185 ms 492404 KB ok
8 Correct 199 ms 492460 KB ok
9 Correct 201 ms 492352 KB ok
10 Correct 186 ms 492444 KB ok
11 Correct 198 ms 492380 KB ok
12 Correct 221 ms 492444 KB ok
13 Correct 192 ms 492412 KB ok
14 Correct 201 ms 492460 KB ok
15 Correct 192 ms 492384 KB ok
16 Correct 195 ms 492352 KB ok
17 Correct 203 ms 492348 KB ok
18 Correct 195 ms 492376 KB ok
19 Correct 192 ms 492416 KB ok
20 Correct 197 ms 492424 KB ok
21 Correct 195 ms 492364 KB ok
22 Correct 183 ms 492400 KB ok
23 Correct 210 ms 492428 KB ok
24 Correct 194 ms 492472 KB ok
25 Correct 190 ms 492424 KB ok
26 Correct 193 ms 492448 KB ok
27 Correct 188 ms 492432 KB ok
28 Correct 218 ms 492356 KB ok
29 Correct 202 ms 492364 KB ok
30 Correct 231 ms 492440 KB ok
31 Correct 214 ms 492424 KB ok
32 Correct 209 ms 492448 KB ok
33 Correct 184 ms 492428 KB ok
34 Correct 211 ms 492464 KB ok
35 Correct 204 ms 492460 KB ok
36 Correct 203 ms 492456 KB ok
37 Correct 187 ms 492460 KB ok
38 Correct 232 ms 492464 KB ok
39 Correct 233 ms 492348 KB ok
40 Correct 213 ms 492460 KB ok
41 Correct 246 ms 492572 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 492456 KB ok
2 Correct 149 ms 492344 KB ok
3 Correct 147 ms 492364 KB ok
4 Correct 223 ms 492404 KB ok
5 Correct 194 ms 492352 KB ok
6 Correct 234 ms 492460 KB ok
7 Correct 185 ms 492404 KB ok
8 Correct 199 ms 492460 KB ok
9 Correct 201 ms 492352 KB ok
10 Correct 186 ms 492444 KB ok
11 Correct 198 ms 492380 KB ok
12 Correct 221 ms 492444 KB ok
13 Correct 192 ms 492412 KB ok
14 Correct 201 ms 492460 KB ok
15 Correct 192 ms 492384 KB ok
16 Correct 195 ms 492352 KB ok
17 Correct 203 ms 492348 KB ok
18 Correct 195 ms 492376 KB ok
19 Correct 192 ms 492416 KB ok
20 Correct 197 ms 492424 KB ok
21 Correct 195 ms 492364 KB ok
22 Correct 183 ms 492400 KB ok
23 Correct 210 ms 492428 KB ok
24 Correct 194 ms 492472 KB ok
25 Correct 190 ms 492424 KB ok
26 Correct 193 ms 492448 KB ok
27 Correct 188 ms 492432 KB ok
28 Correct 218 ms 492356 KB ok
29 Correct 202 ms 492364 KB ok
30 Correct 231 ms 492440 KB ok
31 Correct 214 ms 492424 KB ok
32 Correct 209 ms 492448 KB ok
33 Correct 184 ms 492428 KB ok
34 Correct 211 ms 492464 KB ok
35 Correct 204 ms 492460 KB ok
36 Correct 203 ms 492456 KB ok
37 Correct 187 ms 492460 KB ok
38 Correct 232 ms 492464 KB ok
39 Correct 233 ms 492348 KB ok
40 Correct 213 ms 492460 KB ok
41 Correct 246 ms 492572 KB ok
42 Execution timed out 4609 ms 495484 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 492456 KB ok
2 Correct 149 ms 492344 KB ok
3 Correct 147 ms 492364 KB ok
4 Correct 223 ms 492404 KB ok
5 Correct 194 ms 492352 KB ok
6 Correct 196 ms 492456 KB ok
7 Correct 201 ms 492440 KB ok
8 Execution timed out 4590 ms 492496 KB Time limit exceeded
9 Halted 0 ms 0 KB -