oj.uz

Submission #842674

# Submission time Handle Problem Language Result Execution time Memory
842674 2023-09-03T08:21:52 Z nonono Soccer Stadium (IOI23_soccer) C++17
70 / 100
 691 ms 505684 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

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;
}

int sub5(int N, vector<vector<int>> F) {
    vector<vector<int>> sum(N, vector<int> (N, 0)), high(N, vector<int> (N, 0));
     vector<vector<vector<int>>> low(N, vector<vector<int>> (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 0 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 6 ms 4956 KB ok
8 Correct 691 ms 505372 KB ok
9 Correct 233 ms 47640 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 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 344 KB ok
12 Correct 1 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 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 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 344 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 600 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 344 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 344 KB ok

Subtask #4
18.0 / 18.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 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 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 344 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 600 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 344 KB ok
29 Correct 0 ms 344 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 0 ms 356 KB ok
40 Correct 0 ms 592 KB ok
41 Correct 1 ms 348 KB ok

Subtask #5
16.0 / 16.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 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 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 344 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 600 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 344 KB ok
29 Correct 0 ms 344 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 0 ms 356 KB ok
40 Correct 0 ms 592 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 437 ms 505260 KB ok
43 Correct 413 ms 505340 KB ok
44 Correct 560 ms 505432 KB ok
45 Correct 591 ms 505436 KB ok
46 Correct 440 ms 505428 KB ok
47 Correct 671 ms 505368 KB ok
48 Correct 506 ms 505432 KB ok
49 Correct 543 ms 505512 KB ok
50 Correct 538 ms 505620 KB ok
51 Correct 471 ms 505568 KB ok
52 Correct 410 ms 505236 KB ok
53 Correct 395 ms 505508 KB ok
54 Correct 411 ms 505496 KB ok
55 Correct 427 ms 505432 KB ok
56 Correct 490 ms 505684 KB ok
57 Correct 604 ms 505432 KB ok
58 Correct 604 ms 505224 KB ok
59 Correct 592 ms 505220 KB ok

Subtask #6
0.0 / 30.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 1 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 6 ms 4956 KB ok
9 Correct 691 ms 505372 KB ok
10 Correct 233 ms 47640 KB ok
11 Correct 0 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 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 600 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 344 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 344 KB ok
34 Correct 0 ms 344 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 344 KB ok
42 Correct 1 ms 344 KB ok
43 Correct 1 ms 348 KB ok
44 Correct 0 ms 356 KB ok
45 Correct 0 ms 592 KB ok
46 Correct 1 ms 348 KB ok
47 Correct 437 ms 505260 KB ok
48 Correct 413 ms 505340 KB ok
49 Correct 560 ms 505432 KB ok
50 Correct 591 ms 505436 KB ok
51 Correct 440 ms 505428 KB ok
52 Correct 671 ms 505368 KB ok
53 Correct 506 ms 505432 KB ok
54 Correct 543 ms 505512 KB ok
55 Correct 538 ms 505620 KB ok
56 Correct 471 ms 505568 KB ok
57 Correct 410 ms 505236 KB ok
58 Correct 395 ms 505508 KB ok
59 Correct 411 ms 505496 KB ok
60 Correct 427 ms 505432 KB ok
61 Correct 490 ms 505684 KB ok
62 Correct 604 ms 505432 KB ok
63 Correct 604 ms 505224 KB ok
64 Correct 592 ms 505220 KB ok
65 Partially correct 236 ms 49728 KB partial
66 Partially correct 413 ms 49688 KB partial
67 Partially correct 231 ms 49688 KB partial
68 Partially correct 250 ms 49924 KB partial
69 Partially correct 224 ms 47440 KB partial
70 Partially correct 226 ms 47380 KB partial
71 Partially correct 243 ms 47364 KB partial
72 Partially correct 240 ms 47384 KB partial
73 Incorrect 226 ms 47444 KB wrong
74 Halted 0 ms 0 KB -