oj.uz

Submission #845820

# Submission time Handle Problem Language Result Execution time Memory
845820 2023-09-06T16:00:59 Z Sorting Soccer Stadium (IOI23_soccer) C++17
64 / 100
 2165 ms 752944 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 3;

bool f[N][N];
int prefix[N][N];
short p2[N][N][N], prv[N][N][N], nxt[N][N][N];
int n;

int dp[2][N][N];

int get_sum(int i, int l, int r){
    if(l == 0)
        return prefix[i][r];
    return prefix[i][r] - prefix[i][l - 1];
}

bool bad(int l1, int r1, int l2, int r2){
    if(l1 <= l2 && r2 <= r1)
        return false;
    if(l2 <= l1 && r1 <= r2)
        return false;
    return true;
}

pair<int, int> extend(int i, int j, int l, int r){
    assert(prv[l][r][i] == prv[l][r][j]);
    assert(nxt[l][r][i] == nxt[l][r][j]);
    return {prv[l][r][i], nxt[l][r][j]};
}

int global_ans = 0;

void init_dp(){
    for(int l = n - 1; l >= 0; --l){
        for(int r = l; r < n; ++r){
            for(int i = 0; i < n; ++i){
                if(p2[l][r][i])
                    continue;
                auto [p, q] = extend(i, i, l, r);

                auto &ans = dp[l & 1][r][p];
                ans = 0;

                if(l != r){
                    vector<pair<int, int>> v{{l + 1, r}, {l, r - 1}};
                    for(auto [l2, r2]: v){
                        auto [p2, q2] = extend(p, q, l2, r2);

                        int cand = (p - p2 + q2 - q) * (r2 - l2 + 1);
                        cand += dp[l2 & 1][r2][p2];
                        ans = max(ans, cand);
                    }
                }

                global_ans = max(global_ans, ans + (q - p + 1) * (r - l + 1));
            }
        }
    }
}

int biggest_stadium(int _N, std::vector<std::vector<int>> F){
    n = _N;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            f[i][j] = F[i][j];

    for(int i = 0; i < n; ++i){
        prefix[i][0] = f[i][0];
        for(int j = 1; j < n; ++j)
            prefix[i][j] = prefix[i][j - 1] + f[i][j];
    }

    for(int l = 0; l < n; ++l){
        for(int r = l; r < n; ++r){
            for(int i = 0; i < n; ++i){
                p2[l][r][i] = (bool)get_sum(i, l, r);
            }
        }
    }

    for(int l = 0; l < n; ++l){
        for(int r = l; r < n; ++r){
            int x = 0;
            for(int i = 0; i < n; ++i){
                if(p2[l][r][i]){
                    x = i + 1;
                }
                else{
                    prv[l][r][i] = x;
                }
            }

            x = n - 1;
            for(int i = n - 1; i >= 0; --i){
                if(p2[l][r][i]){
                    x = i - 1;
                }
                else{
                    nxt[l][r][i] = x;
                }
            }
        }
    }

    init_dp();

    return global_ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 3 ms 20824 KB ok
4 Correct 3 ms 22876 KB ok
5 Correct 1 ms 8536 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 41 ms 156788 KB ok
8 Correct 2165 ms 752848 KB ok
9 Runtime error 293 ms 36128 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 2 ms 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12632 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 1 ms 12636 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 2 ms 12716 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 12636 KB ok
11 Correct 1 ms 12636 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 12636 KB ok

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 3 ms 20824 KB ok
5 Correct 3 ms 22876 KB ok
6 Correct 2 ms 12632 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 1 ms 12636 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 12636 KB ok
11 Correct 2 ms 12716 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 1 ms 12636 KB ok
15 Correct 2 ms 12636 KB ok
16 Correct 2 ms 12636 KB ok
17 Correct 3 ms 18780 KB ok
18 Correct 2 ms 18908 KB ok
19 Correct 2 ms 18780 KB ok
20 Correct 2 ms 18780 KB ok
21 Correct 3 ms 18780 KB ok
22 Correct 3 ms 18780 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 14684 KB ok
25 Correct 2 ms 14684 KB ok
26 Correct 2 ms 16732 KB ok
27 Correct 2 ms 18780 KB ok
28 Correct 2 ms 18776 KB ok
29 Correct 2 ms 18780 KB ok
30 Correct 7 ms 51804 KB ok
31 Correct 5 ms 51804 KB ok
32 Correct 6 ms 51804 KB ok
33 Correct 6 ms 51804 KB ok
34 Correct 5 ms 51800 KB ok
35 Correct 5 ms 49756 KB ok
36 Correct 4 ms 37212 KB ok
37 Correct 5 ms 41564 KB ok
38 Correct 4 ms 39516 KB ok
39 Correct 5 ms 41564 KB ok
40 Correct 7 ms 51800 KB ok
41 Correct 6 ms 51800 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 3 ms 20824 KB ok
5 Correct 3 ms 22876 KB ok
6 Correct 2 ms 12632 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 1 ms 12636 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 12636 KB ok
11 Correct 2 ms 12716 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 1 ms 12636 KB ok
15 Correct 2 ms 12636 KB ok
16 Correct 2 ms 12636 KB ok
17 Correct 3 ms 18780 KB ok
18 Correct 2 ms 18908 KB ok
19 Correct 2 ms 18780 KB ok
20 Correct 2 ms 18780 KB ok
21 Correct 3 ms 18780 KB ok
22 Correct 3 ms 18780 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 14684 KB ok
25 Correct 2 ms 14684 KB ok
26 Correct 2 ms 16732 KB ok
27 Correct 2 ms 18780 KB ok
28 Correct 2 ms 18776 KB ok
29 Correct 2 ms 18780 KB ok
30 Correct 7 ms 51804 KB ok
31 Correct 5 ms 51804 KB ok
32 Correct 6 ms 51804 KB ok
33 Correct 6 ms 51804 KB ok
34 Correct 5 ms 51800 KB ok
35 Correct 5 ms 49756 KB ok
36 Correct 4 ms 37212 KB ok
37 Correct 5 ms 41564 KB ok
38 Correct 4 ms 39516 KB ok
39 Correct 5 ms 41564 KB ok
40 Correct 7 ms 51800 KB ok
41 Correct 6 ms 51800 KB ok
42 Correct 361 ms 752584 KB ok
43 Correct 312 ms 752588 KB ok
44 Correct 973 ms 752736 KB ok
45 Correct 1300 ms 752920 KB ok
46 Correct 464 ms 752724 KB ok
47 Correct 1955 ms 752768 KB ok
48 Correct 842 ms 752664 KB ok
49 Correct 891 ms 752724 KB ok
50 Correct 1199 ms 752720 KB ok
51 Correct 517 ms 752548 KB ok
52 Correct 311 ms 508488 KB ok
53 Correct 251 ms 457016 KB ok
54 Correct 307 ms 498196 KB ok
55 Correct 369 ms 543284 KB ok
56 Correct 910 ms 752752 KB ok
57 Correct 1389 ms 752588 KB ok
58 Correct 1336 ms 752840 KB ok
59 Correct 1265 ms 752944 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 3 ms 20824 KB ok
5 Correct 3 ms 22876 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 41 ms 156788 KB ok
9 Correct 2165 ms 752848 KB ok
10 Runtime error 293 ms 36128 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -