oj.uz

Submission #845797

# Submission time Handle Problem Language Result Execution time Memory
845797 2023-09-06T15:45:36 Z Sorting Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1845332 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 3;

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

map<array<int, 4>, pair<int, bool>> dp;

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 solve(int i, int j, int l, int r){
    auto &[ans, solved] = dp[{i, j, l, r}];
    if(solved)
        return ans;

    ans = 0;
    solved = true;
    if(l != r){
        vector<pair<int, int>> v{{l + 1, r}, {l, r - 1}};
        for(auto [l2, r2]: v){
            auto [i2, j2] = extend(i, j, l2, r2);

            int cand = (i - i2 + j2 - j) * (r2 - l2 + 1);
            cand += solve(i2, j2, l2, r2);
            ans = max(ans, cand);
        }
    }

    return ans;
}

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

    int ans = 0;
    for(int i = 0; i < n; ++i){
        for(int l = 0; l < n; ++l){
            for(int r = l; r < n; ++r){
                if(f[i][r])
                    break;

                auto [l2, r2] = extend(i, i, l, r);
                ans = max(ans, solve(l2, r2, l, r) + (r - l + 1) * (r2 - l2 + 1));
            }
        }
    }

    return 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 16728 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB ok
2 Correct 1 ms 10584 KB ok
3 Correct 4 ms 29272 KB ok
4 Correct 3 ms 33112 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 75 ms 300868 KB ok
8 Execution timed out 4511 ms 1501488 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 4 ms 29272 KB ok
5 Correct 3 ms 33112 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 1 ms 10584 KB ok
8 Correct 1 ms 10584 KB ok
9 Correct 1 ms 10584 KB ok
10 Correct 1 ms 10584 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10584 KB ok
14 Correct 1 ms 10584 KB ok
15 Correct 1 ms 10584 KB ok
16 Correct 1 ms 10584 KB ok
17 Correct 3 ms 22872 KB ok
18 Correct 2 ms 22872 KB ok
19 Correct 2 ms 22876 KB ok
20 Correct 2 ms 22876 KB ok
21 Correct 3 ms 22872 KB ok
22 Correct 2 ms 16728 KB ok
23 Correct 2 ms 16728 KB ok
24 Correct 2 ms 18776 KB ok
25 Correct 2 ms 18776 KB ok
26 Correct 2 ms 18776 KB ok
27 Correct 2 ms 22872 KB ok
28 Correct 3 ms 22872 KB ok
29 Correct 3 ms 23128 KB ok
30 Correct 10 ms 90972 KB ok
31 Correct 10 ms 90968 KB ok
32 Correct 9 ms 90712 KB ok
33 Correct 9 ms 90648 KB ok
34 Correct 9 ms 84548 KB ok
35 Correct 9 ms 84568 KB ok
36 Correct 7 ms 59992 KB ok
37 Correct 7 ms 64088 KB ok
38 Correct 7 ms 66136 KB ok
39 Correct 7 ms 72248 KB ok
40 Correct 10 ms 90712 KB ok
41 Correct 10 ms 90716 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 4 ms 29272 KB ok
5 Correct 3 ms 33112 KB ok
6 Correct 1 ms 10584 KB ok
7 Correct 1 ms 10584 KB ok
8 Correct 1 ms 10584 KB ok
9 Correct 1 ms 10584 KB ok
10 Correct 1 ms 10584 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10584 KB ok
14 Correct 1 ms 10584 KB ok
15 Correct 1 ms 10584 KB ok
16 Correct 1 ms 10584 KB ok
17 Correct 3 ms 22872 KB ok
18 Correct 2 ms 22872 KB ok
19 Correct 2 ms 22876 KB ok
20 Correct 2 ms 22876 KB ok
21 Correct 3 ms 22872 KB ok
22 Correct 2 ms 16728 KB ok
23 Correct 2 ms 16728 KB ok
24 Correct 2 ms 18776 KB ok
25 Correct 2 ms 18776 KB ok
26 Correct 2 ms 18776 KB ok
27 Correct 2 ms 22872 KB ok
28 Correct 3 ms 22872 KB ok
29 Correct 3 ms 23128 KB ok
30 Correct 10 ms 90972 KB ok
31 Correct 10 ms 90968 KB ok
32 Correct 9 ms 90712 KB ok
33 Correct 9 ms 90648 KB ok
34 Correct 9 ms 84548 KB ok
35 Correct 9 ms 84568 KB ok
36 Correct 7 ms 59992 KB ok
37 Correct 7 ms 64088 KB ok
38 Correct 7 ms 66136 KB ok
39 Correct 7 ms 72248 KB ok
40 Correct 10 ms 90712 KB ok
41 Correct 10 ms 90716 KB ok
42 Correct 1067 ms 1565500 KB ok
43 Correct 641 ms 1527728 KB ok
44 Execution timed out 4546 ms 1845332 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 1 ms 10584 KB ok
4 Correct 4 ms 29272 KB ok
5 Correct 3 ms 33112 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 10584 KB ok
8 Correct 75 ms 300868 KB ok
9 Execution timed out 4511 ms 1501488 KB Time limit exceeded
10 Halted 0 ms 0 KB -