oj.uz

Submission #845810

# Submission time Handle Problem Language Result Execution time Memory
845810 2023-09-06T15:58:16 Z Sorting Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1223252 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;
 
pair<int, bool> dp[N][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 solve(int i, int j, int l, int r){
    auto &[ans, solved] = dp[i][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] = (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;
                }
            }
        }
    }
 
    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;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10740 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 3 ms 20828 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 26 ms 157240 KB ok
8 Correct 4233 ms 754416 KB ok
9 Runtime error 350 ms 36188 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 10740 KB ok
2 Correct 1 ms 10588 KB ok
3 Correct 2 ms 10584 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 10692 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 2 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 10588 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10740 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 2 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 1 ms 10692 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 2 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 2 ms 16732 KB ok
16 Correct 2 ms 16732 KB ok
17 Correct 3 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 2 ms 16732 KB ok
20 Correct 2 ms 12636 KB ok
21 Correct 2 ms 14680 KB ok
22 Correct 2 ms 14684 KB ok
23 Correct 2 ms 14684 KB ok
24 Correct 2 ms 14684 KB ok
25 Correct 2 ms 16728 KB ok
26 Correct 2 ms 16984 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10740 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 3 ms 20828 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10692 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 2 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 3 ms 16732 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 2 ms 12636 KB ok
23 Correct 2 ms 14680 KB ok
24 Correct 2 ms 14684 KB ok
25 Correct 2 ms 14684 KB ok
26 Correct 2 ms 14684 KB ok
27 Correct 2 ms 16728 KB ok
28 Correct 2 ms 16984 KB ok
29 Correct 2 ms 16732 KB ok
30 Correct 7 ms 53084 KB ok
31 Correct 7 ms 53080 KB ok
32 Correct 7 ms 52824 KB ok
33 Correct 6 ms 52060 KB ok
34 Correct 6 ms 49756 KB ok
35 Correct 5 ms 49872 KB ok
36 Correct 4 ms 35420 KB ok
37 Correct 4 ms 39516 KB ok
38 Correct 6 ms 41416 KB ok
39 Correct 5 ms 41820 KB ok
40 Correct 5 ms 51800 KB ok
41 Correct 7 ms 53592 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10740 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 3 ms 20828 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10692 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 2 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 2 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 3 ms 16732 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 2 ms 12636 KB ok
23 Correct 2 ms 14680 KB ok
24 Correct 2 ms 14684 KB ok
25 Correct 2 ms 14684 KB ok
26 Correct 2 ms 14684 KB ok
27 Correct 2 ms 16728 KB ok
28 Correct 2 ms 16984 KB ok
29 Correct 2 ms 16732 KB ok
30 Correct 7 ms 53084 KB ok
31 Correct 7 ms 53080 KB ok
32 Correct 7 ms 52824 KB ok
33 Correct 6 ms 52060 KB ok
34 Correct 6 ms 49756 KB ok
35 Correct 5 ms 49872 KB ok
36 Correct 4 ms 35420 KB ok
37 Correct 4 ms 39516 KB ok
38 Correct 6 ms 41416 KB ok
39 Correct 5 ms 41820 KB ok
40 Correct 5 ms 51800 KB ok
41 Correct 7 ms 53592 KB ok
42 Correct 573 ms 1216948 KB ok
43 Correct 506 ms 1191220 KB ok
44 Correct 2683 ms 1196208 KB ok
45 Correct 3881 ms 1162584 KB ok
46 Correct 751 ms 1223252 KB ok
47 Correct 4030 ms 766680 KB ok
48 Correct 1513 ms 874604 KB ok
49 Correct 1673 ms 884616 KB ok
50 Execution timed out 4568 ms 1047516 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB ok
2 Correct 2 ms 10740 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 3 ms 20828 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 26 ms 157240 KB ok
9 Correct 4233 ms 754416 KB ok
10 Runtime error 350 ms 36188 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -