oj.uz

Submission #845796

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

using namespace std;

const int N = 30;

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 0 ms 344 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Runtime error 2 ms 856 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 1 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 1 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 1 ms 548 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 ms 344 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 344 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 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 1 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 1 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 1 ms 344 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 548 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 344 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 1 ms 344 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 344 KB ok
28 Correct 0 ms 344 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 2 ms 860 KB ok
31 Correct 1 ms 856 KB ok
32 Correct 1 ms 600 KB ok
33 Correct 1 ms 600 KB ok
34 Correct 1 ms 600 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 0 ms 600 KB ok
37 Correct 1 ms 600 KB ok
38 Correct 1 ms 600 KB ok
39 Correct 1 ms 604 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 2 ms 600 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 1 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 1 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 1 ms 344 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 548 KB ok
19 Correct 0 ms 344 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 344 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 1 ms 344 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 344 KB ok
28 Correct 0 ms 344 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 2 ms 860 KB ok
31 Correct 1 ms 856 KB ok
32 Correct 1 ms 600 KB ok
33 Correct 1 ms 600 KB ok
34 Correct 1 ms 600 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 0 ms 600 KB ok
37 Correct 1 ms 600 KB ok
38 Correct 1 ms 600 KB ok
39 Correct 1 ms 604 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 2 ms 600 KB ok
42 Runtime error 18 ms 4432 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Runtime error 2 ms 856 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -