oj.uz

Submission #1025813

# Submission time Handle Problem Language Result Execution time Memory
1025813 2024-07-17T10:23:02 Z thinknoexit Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 146448 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2020;
int n;
int f[N][N], qs[N][N];
int l[N], r[N];
int mx;
int l1[N][N], r1[N][N];
int L1[N], R1[N];
int dp[N][N], L[N][N], R[N][N];
int inter(int l1, int r1, int l2, int r2) {
    if (l1 > l2) {
        swap(l1, l2);
        swap(r1, r2);
    }
    // l1 <= l2
    if (r2 <= r1) return r2 - l2 + 1;
    if (r1 < l2) return 0;
    return r1 - l2 + 1;
}
int biggest_stadium(int NN, vector<vector<int>> F) {
    n = NN;
    for (int i = 1;i <= n;i++) {
        f[0][i] = f[n + 1][i] = f[i][0] = f[i][n + 1] = 1;
        for (int j = 1;j <= n;j++) {
            f[i][j] = F[i - 1][j - 1];
            qs[i][j] = qs[i][j - 1] + f[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= n;j++) {
            if (f[i][j] == 1) l1[i][j] = j + 1;
            else l1[i][j] = l1[i][j - 1];
        }
        for (int j = n + 1;j >= 1;j--) {
            if (f[i][j] == 1) r1[i][j] = j - 1;
            else r1[i][j] = r1[i][j + 1];
        }
    }
    mx = 0;
    for (int c = 1;c <= n;c++) {
        for (int i = 1;i <= n;i++) {
            if (f[i][c]) dp[i][i] = -1e9, L[i][i] = L1[i] = -1, R[i][i] = R1[i] = -2;
            else {
                L1[i] = l1[i][c], R1[i] = r1[i][c];
                dp[i][i] = R1[i] - L1[i] + 1, L[i][i] = L1[i], R[i][i] = R1[i];
                mx = max(mx, dp[i][i]);
            }
        }
        for (int k = 1;k < n;k++) {
            for (int i = 1;i <= n - k;i++) {
                int j = i + k;
                L[i][j] = max(L[i + 1][j], L1[i]), R[i][j] = min(R[i + 1][j], R1[i]);
                dp[i][j] = -1e9;
                if (inter(L[i + 1][j], R[i + 1][j], L1[i], R1[i]) != 0) {
                    dp[i][j] = max(dp[i][j], dp[i + 1][j] + inter(L[i + 1][j], R[i + 1][j], L1[i], R1[i]));
                }
                if (inter(L[i][j - 1], R[i][j - 1], L1[j], R1[j]) != 0) {
                    dp[i][j] = max(dp[i][j], dp[i][j - 1] + inter(L[i][j - 1], R[i][j - 1], L1[j], R1[j]));
                }
                mx = max(mx, dp[i][j]);
            }
        }
    }
    return mx;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 5 ms 19036 KB ok
8 Correct 270 ms 38872 KB ok
9 Execution timed out 4567 ms 146448 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 2 ms 10588 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 2 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 1 ms 10584 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 1 ms 10588 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10584 KB ok
22 Correct 1 ms 10584 KB ok
23 Correct 1 ms 10584 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 1 ms 10584 KB ok
26 Correct 1 ms 10588 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 2 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10588 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 1 ms 10584 KB ok
24 Correct 1 ms 10584 KB ok
25 Correct 1 ms 10584 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 1 ms 10584 KB ok
28 Correct 1 ms 10588 KB ok
29 Correct 1 ms 10588 KB ok
30 Correct 2 ms 12892 KB ok
31 Correct 2 ms 12892 KB ok
32 Correct 2 ms 12888 KB ok
33 Correct 2 ms 12888 KB ok
34 Correct 2 ms 12892 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 12892 KB ok
37 Correct 2 ms 12972 KB ok
38 Correct 2 ms 12892 KB ok
39 Correct 1 ms 12892 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 1 ms 12892 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 2 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10588 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 1 ms 10584 KB ok
24 Correct 1 ms 10584 KB ok
25 Correct 1 ms 10584 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 1 ms 10584 KB ok
28 Correct 1 ms 10588 KB ok
29 Correct 1 ms 10588 KB ok
30 Correct 2 ms 12892 KB ok
31 Correct 2 ms 12892 KB ok
32 Correct 2 ms 12888 KB ok
33 Correct 2 ms 12888 KB ok
34 Correct 2 ms 12892 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 12892 KB ok
37 Correct 2 ms 12972 KB ok
38 Correct 2 ms 12892 KB ok
39 Correct 1 ms 12892 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 1 ms 12892 KB ok
42 Correct 363 ms 38876 KB ok
43 Correct 394 ms 38872 KB ok
44 Correct 306 ms 38876 KB ok
45 Correct 297 ms 38744 KB ok
46 Correct 316 ms 39504 KB ok
47 Correct 276 ms 39368 KB ok
48 Correct 277 ms 39304 KB ok
49 Correct 268 ms 39256 KB ok
50 Correct 269 ms 39260 KB ok
51 Correct 357 ms 39372 KB ok
52 Correct 252 ms 39368 KB ok
53 Correct 240 ms 39364 KB ok
54 Correct 242 ms 39256 KB ok
55 Correct 255 ms 39252 KB ok
56 Correct 249 ms 39304 KB ok
57 Correct 282 ms 39368 KB ok
58 Correct 279 ms 39368 KB ok
59 Correct 314 ms 39252 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 5 ms 19036 KB ok
9 Correct 270 ms 38872 KB ok
10 Execution timed out 4567 ms 146448 KB Time limit exceeded
11 Halted 0 ms 0 KB -