oj.uz

Submission #1067744

# Submission time Handle Problem Language Result Execution time Memory
1067744 2024-08-21T02:46:45 Z becaido Soccer Stadium (IOI23_soccer) C++17
64 / 100
 588 ms 754000 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;
int a[SIZE][SIZE], L[SIZE][SIZE][SIZE], R[SIZE][SIZE][SIZE], dp[SIZE][SIZE][SIZE];

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];
    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 0 ms 604 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 800 KB ok
4 Correct 1 ms 860 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 14 ms 31832 KB ok
8 Correct 425 ms 753956 KB ok
9 Runtime error 221 ms 40532 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 0 ms 348 KB ok
2 Correct 1 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 1 ms 344 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 0 ms 604 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 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 1 ms 344 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 1 ms 600 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 600 KB ok
23 Correct 1 ms 600 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 456 KB ok
26 Correct 0 ms 600 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 800 KB ok
5 Correct 1 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 1 ms 344 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 1 ms 600 KB ok
19 Correct 1 ms 600 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 600 KB ok
25 Correct 1 ms 600 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 456 KB ok
28 Correct 0 ms 600 KB ok
29 Correct 1 ms 604 KB ok
30 Correct 1 ms 3420 KB ok
31 Correct 1 ms 3164 KB ok
32 Correct 1 ms 1368 KB ok
33 Correct 1 ms 964 KB ok
34 Correct 2 ms 3420 KB ok
35 Correct 1 ms 1884 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1628 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 3420 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 800 KB ok
5 Correct 1 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 1 ms 344 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 1 ms 600 KB ok
19 Correct 1 ms 600 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 600 KB ok
25 Correct 1 ms 600 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 456 KB ok
28 Correct 0 ms 600 KB ok
29 Correct 1 ms 604 KB ok
30 Correct 1 ms 3420 KB ok
31 Correct 1 ms 3164 KB ok
32 Correct 1 ms 1368 KB ok
33 Correct 1 ms 964 KB ok
34 Correct 2 ms 3420 KB ok
35 Correct 1 ms 1884 KB ok
36 Correct 1 ms 1372 KB ok
37 Correct 1 ms 1628 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 3420 KB ok
42 Correct 257 ms 182396 KB ok
43 Correct 217 ms 98640 KB ok
44 Correct 460 ms 753748 KB ok
45 Correct 588 ms 753900 KB ok
46 Correct 320 ms 385696 KB ok
47 Correct 449 ms 754000 KB ok
48 Correct 404 ms 734088 KB ok
49 Correct 379 ms 676688 KB ok
50 Correct 471 ms 753892 KB ok
51 Correct 302 ms 381948 KB ok
52 Correct 199 ms 241084 KB ok
53 Correct 155 ms 67152 KB ok
54 Correct 240 ms 270220 KB ok
55 Correct 364 ms 610128 KB ok
56 Correct 215 ms 187976 KB ok
57 Correct 414 ms 753440 KB ok
58 Correct 420 ms 748624 KB ok
59 Correct 418 ms 722780 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 800 KB ok
5 Correct 1 ms 860 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 14 ms 31832 KB ok
9 Correct 425 ms 753956 KB ok
10 Runtime error 221 ms 40532 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -