oj.uz

Submission #842671

# Submission time Handle Problem Language Result Execution time Memory
842671 2023-09-03T08:19:57 Z nonono Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1726944 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 505;

void upMax(int &x, int y) {
    x = max(x, y);
}

int sub1(int N, vector<vector<int>> F) {
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(F[i][j] == 1) {
                return max({
                    N * i + N * j - i * j,
                    N * i + N * (N - j - 1) - i * (N - j - 1),
                    N * (N - i - 1) + N * j - (N - i - 1) * j,
                    N * (N - i - 1) + N * (N - j - 1) - (N - i - 1) * (N - j - 1)
                });
            }
        }
    }

    return N * N;
}

map<int, int> low[mxN][mxN];

int sub5(int N, vector<vector<int>> F) {
    vector<vector<int>> sum(N, vector<int> (N, 0)), high(N, vector<int> (N, 0));

    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            sum[i][j] = (j ? sum[i][j - 1] : 0) + F[i][j];
        }
    }

    auto get_sum = [&] (int row, int l, int r) {
        return sum[row][r] - (!l ? 0 : sum[row][l - 1]);
    };

    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            high[i][j] = (F[i][j] ? 0 : (i ? high[i - 1][j] : 0) + 1);
        }
    }

    for(int i = 0; i < N; i ++) {
        for(int k = 0; k < N; k ++) {
            int x = high[i][k];

            for(int j = k; j >= 0; j --) {
                x = min(x, high[i][j]);
                low[i][j][k] = x;
            }
        }
    }

    vector<vector<int>> dp(N, vector<int> (N, 0));
    int result = 0;

    for(int row = 0; row < N; row ++) {
        for(int i = 0; i < N; i ++) {
            for(int j = i; j < N; j ++) {
                if(get_sum(row, i, j)) dp[i][j] = 0;
            }
        }

        for(int i = 0, j = 0; i < N; i = j + 1) {
            for(j = i; j + 1 < N && F[row][j + 1] == F[row][i]; ) j ++ ;
            if(F[row][i]) continue ;

            for(int k = (j - i + 1); k > 0; k --) {
                for(int l = i; l + k - 1 <= j; l ++) {
                    int r = l + k - 1;

                    if(k > 1) {
                        if(l + 1 < N) upMax(dp[l + 1][r], dp[l][r] + low[row][l][r]);
                        if(r - 1 >= 0) upMax(dp[l][r - 1], dp[l][r] + low[row][l][r]);
                    } else {
                        upMax(result, dp[l][r] + low[row][l][r]);
                    }
                }
            }
        }
    }

    return result;
}

int biggest_stadium(int N, vector<vector<int>> F) {
    if(N <= 500) return sub5(N, F);
    return sub1(N, F);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB ok
2 Correct 3 ms 12380 KB ok
3 Correct 3 ms 12380 KB ok
4 Correct 3 ms 12380 KB ok
5 Correct 3 ms 12380 KB ok
6 Correct 3 ms 12380 KB ok
7 Correct 67 ms 36136 KB ok
8 Execution timed out 4601 ms 1726944 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB ok
2 Correct 3 ms 12380 KB ok
3 Correct 3 ms 12380 KB ok
4 Correct 3 ms 12380 KB ok
5 Correct 3 ms 12380 KB ok
6 Correct 2 ms 12380 KB ok
7 Correct 3 ms 12380 KB ok
8 Correct 3 ms 12380 KB ok
9 Correct 3 ms 12380 KB ok
10 Correct 3 ms 12376 KB ok
11 Correct 3 ms 12380 KB ok
12 Correct 3 ms 12380 KB ok
13 Correct 2 ms 12380 KB ok
14 Correct 3 ms 12380 KB ok
15 Correct 2 ms 12380 KB ok
16 Correct 3 ms 12376 KB ok
17 Correct 3 ms 12380 KB ok
18 Correct 3 ms 12380 KB ok
19 Correct 3 ms 12380 KB ok
20 Correct 3 ms 12380 KB ok
21 Correct 3 ms 12380 KB ok
22 Correct 3 ms 12380 KB ok
23 Correct 3 ms 12376 KB ok
24 Correct 3 ms 12380 KB ok
25 Correct 3 ms 12376 KB ok
26 Correct 3 ms 12380 KB ok
27 Correct 3 ms 12380 KB ok
28 Correct 3 ms 12636 KB ok
29 Correct 3 ms 12380 KB ok
30 Correct 4 ms 12892 KB ok
31 Correct 4 ms 12892 KB ok
32 Correct 4 ms 12908 KB ok
33 Correct 4 ms 12888 KB ok
34 Correct 5 ms 12888 KB ok
35 Correct 5 ms 13144 KB ok
36 Correct 4 ms 12892 KB ok
37 Correct 4 ms 12892 KB ok
38 Correct 4 ms 12892 KB ok
39 Correct 4 ms 12892 KB ok
40 Correct 4 ms 12904 KB ok
41 Correct 4 ms 12892 KB ok
42 Execution timed out 4610 ms 1704944 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB ok
2 Correct 3 ms 12380 KB ok
3 Correct 3 ms 12380 KB ok
4 Correct 3 ms 12380 KB ok
5 Correct 3 ms 12380 KB ok
6 Correct 3 ms 12380 KB ok
7 Correct 3 ms 12380 KB ok
8 Correct 67 ms 36136 KB ok
9 Execution timed out 4601 ms 1726944 KB Time limit exceeded
10 Halted 0 ms 0 KB -