oj.uz

Submission #1067759

# Submission time Handle Problem Language Result Execution time Memory
1067759 2024-08-21T02:54:23 Z becaido Soccer Stadium (IOI23_soccer) C++17
70 / 100
 433 ms 754004 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "soccer.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 505;

int n, ans;
bool a[SIZE << 2][SIZE << 2];
int L[SIZE][SIZE][SIZE], R[SIZE][SIZE][SIZE], dp[SIZE][SIZE][SIZE];

int big() {
    int cnt = 0, x = 0, y = 0;
    FOR (i, 1, n) FOR (j, 1, n) if (a[i][j]) {
        cnt++;
        x = i, y = j;
    }
    if (cnt == 0) return n * n;
    if (cnt == 1) return n * n - min(x, n - x + 1) * min(y, n - y + 1);
    {
        vector<pair<int, int>> seg;
        FOR (i, 1, n) {
            vector<pair<int, int>> v;
            int l = 0;
            FOR (j, 1, n) if (a[i][j] == 0) {
                if (l == 0) l = j;
                if (j == n || a[i][j + 1]) {
                    v.pb(l, j);
                    l = 0;
                }
            }
            if (v.size() > 1) return 0;
            seg.insert(seg.end(), v.begin(), v.end());
        }
        sort(seg.begin(), seg.end(), [&](auto x, auto y) {
            return x.F != y.F ? x.F < y.F : x.S > y.S;
        });
        FOR (i, 1, seg.size() - 1) {
            auto [pl, pr] = seg[i - 1];
            auto [l, r] = seg[i];
            if (l < pl || r > pr) return 0;
        }
    }
    {
        vector<pair<int, int>> seg;
        FOR (i, 1, n) {
            vector<pair<int, int>> v;
            int l = 0;
            FOR (j, 1, n) if (a[j][i] == 0) {
                if (l == 0) l = j;
                if (j == n || a[j][i + 1]) {
                    v.pb(l, j);
                    l = 0;
                }
            }
            if (v.size() > 1) return 0;
            seg.insert(seg.end(), v.begin(), v.end());
        }
        sort(seg.begin(), seg.end(), [&](auto x, auto y) {
            return x.F != y.F ? x.F < y.F : x.S > y.S;
        });
        FOR (i, 1, seg.size() - 1) {
            auto [pl, pr] = seg[i - 1];
            auto [l, r] = seg[i];
            if (l < pl || r > pr) return 0;
        }
    }
    return n * n - cnt;
}

int biggest_stadium(int N, vector<vector<int>> F) {
    n = N;
    FOR (i, 1, n) FOR (j, 1, n) a[i][j] = F[i - 1][j - 1];
    if (n > 500) return big();
    FOR (i, 1, n) {
        FOR (j, 1, n) if (a[i][j] == 0) L[i][i][j] = (j > 1 && a[i][j - 1] == 0 ? L[i][i][j - 1] : j);
        for (int j = n; j >= 1; j--) if (a[i][j] == 0) R[i][i][j] = (j < n && a[i][j + 1] == 0 ? R[i][i][j + 1] : j);
    }
    FOR (u, 1, n) FOR (d, u + 1, n) FOR (j, 1, n) {
        if (L[u][d - 1][j] && L[d][d][j]) L[u][d][j] = max(L[u][d - 1][j], L[d][d][j]);
        if (R[u][d - 1][j] && R[d][d][j]) R[u][d][j] = min(R[u][d - 1][j], R[d][d][j]);
    }
    FOR (i, 1, n) FOR (j, 1, n) if (L[i][i][j]) dp[i][i][j] = R[i][i][j] - L[i][i][j] + 1, ans = max(ans, dp[i][i][j]);
    FOR (d, 1, n) for (int u = d - 1; u >= 1; u--) FOR (j, 1, n) if (L[u][d][j]) {
        dp[u][d][j] = max(dp[u][d - 1][j], dp[u + 1][d][j]) + R[u][d][j] - L[u][d][j] + 1;
        ans = max(ans, dp[u][d][j]);
    }
    return ans;
}

/*
in1
5
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
out1
20
*/

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 860 KB ok
4 Correct 0 ms 860 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 13 ms 31788 KB ok
8 Correct 416 ms 753872 KB ok
9 Correct 222 ms 42832 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 860 KB ok
5 Correct 0 ms 860 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 600 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 3420 KB ok
31 Correct 1 ms 3164 KB ok
32 Correct 1 ms 1372 KB ok
33 Correct 1 ms 860 KB ok
34 Correct 1 ms 3420 KB ok
35 Correct 1 ms 1676 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1472 KB ok
38 Correct 1 ms 1628 KB ok
39 Correct 1 ms 1884 KB ok
40 Correct 1 ms 2140 KB ok
41 Correct 1 ms 3416 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 860 KB ok
5 Correct 0 ms 860 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 600 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 3420 KB ok
31 Correct 1 ms 3164 KB ok
32 Correct 1 ms 1372 KB ok
33 Correct 1 ms 860 KB ok
34 Correct 1 ms 3420 KB ok
35 Correct 1 ms 1676 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1472 KB ok
38 Correct 1 ms 1628 KB ok
39 Correct 1 ms 1884 KB ok
40 Correct 1 ms 2140 KB ok
41 Correct 1 ms 3416 KB ok
42 Correct 254 ms 182520 KB ok
43 Correct 213 ms 98520 KB ok
44 Correct 406 ms 753744 KB ok
45 Correct 413 ms 753752 KB ok
46 Correct 302 ms 385872 KB ok
47 Correct 433 ms 753976 KB ok
48 Correct 389 ms 734032 KB ok
49 Correct 379 ms 676692 KB ok
50 Correct 389 ms 754004 KB ok
51 Correct 293 ms 381780 KB ok
52 Correct 202 ms 240968 KB ok
53 Correct 134 ms 67220 KB ok
54 Correct 240 ms 270060 KB ok
55 Correct 345 ms 610128 KB ok
56 Correct 217 ms 187988 KB ok
57 Correct 406 ms 753492 KB ok
58 Correct 412 ms 748372 KB ok
59 Correct 408 ms 722772 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 860 KB ok
5 Correct 0 ms 860 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 13 ms 31788 KB ok
9 Correct 416 ms 753872 KB ok
10 Correct 222 ms 42832 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 600 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 0 ms 604 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 604 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 0 ms 604 KB ok
35 Correct 1 ms 3420 KB ok
36 Correct 1 ms 3164 KB ok
37 Correct 1 ms 1372 KB ok
38 Correct 1 ms 860 KB ok
39 Correct 1 ms 3420 KB ok
40 Correct 1 ms 1676 KB ok
41 Correct 1 ms 1372 KB ok
42 Correct 1 ms 1472 KB ok
43 Correct 1 ms 1628 KB ok
44 Correct 1 ms 1884 KB ok
45 Correct 1 ms 2140 KB ok
46 Correct 1 ms 3416 KB ok
47 Correct 254 ms 182520 KB ok
48 Correct 213 ms 98520 KB ok
49 Correct 406 ms 753744 KB ok
50 Correct 413 ms 753752 KB ok
51 Correct 302 ms 385872 KB ok
52 Correct 433 ms 753976 KB ok
53 Correct 389 ms 734032 KB ok
54 Correct 379 ms 676692 KB ok
55 Correct 389 ms 754004 KB ok
56 Correct 293 ms 381780 KB ok
57 Correct 202 ms 240968 KB ok
58 Correct 134 ms 67220 KB ok
59 Correct 240 ms 270060 KB ok
60 Correct 345 ms 610128 KB ok
61 Correct 217 ms 187988 KB ok
62 Correct 406 ms 753492 KB ok
63 Correct 412 ms 748372 KB ok
64 Correct 408 ms 722772 KB ok
65 Partially correct 200 ms 43560 KB partial
66 Partially correct 220 ms 43548 KB partial
67 Partially correct 203 ms 43540 KB partial
68 Partially correct 193 ms 43604 KB partial
69 Partially correct 191 ms 43552 KB partial
70 Partially correct 211 ms 43604 KB partial
71 Partially correct 189 ms 43600 KB partial
72 Partially correct 192 ms 43600 KB partial
73 Incorrect 200 ms 43456 KB wrong
74 Halted 0 ms 0 KB -