oj.uz

Submission #840710

# Submission time Handle Problem Language Result Execution time Memory
840710 2023-08-31T16:09:14 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 362724 KB 
#include "soccer.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 2e3+10;
 
struct Sparse {
    vector<vector<int>> sparse;
    Sparse() {}
    Sparse(vector<int>& v) {
        int n = v.size();
        sparse.push_back(v);
        for (int i = 1; (1 << i) <= n; i++) {
            sparse.push_back(vector<int>(n - (1 << i) + 1));
            for (int j = 0; j + (1 << i) <= n; j++) {
                sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]);
            }
        }
    }
 
    int qry(int l, int r) {
        assert(l <= r);
        int b = 31 - __builtin_clz(r - l + 1);
        // cerr << "> " << l << ' ' << r << ''
        return min(sparse[b][l], sparse[b][r - (1 << b) + 1]);
    }
} ones[M], twos[M];
 
int get_cost(int i, int l, int r) {
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}
 
vector<int> impl[M][M];
vector<int> impr[M][M];
vector<int> has[M][M];
gp_hash_table<ll, int> dp;
 
ll h(int a, int b, int c) {
    return (long long) a * M * M + b * M + c;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
     for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            while (i - up[j] >= 0 && !F[i - up[j]][j]) up[j]++;
            while (i + down[j] < N && !F[i + down[j]][j]) down[j]++;
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
    }
 
    auto add_imp = [&](int i, int l, int r) {
        has[l][r].push_back(i);
        impl[i][l].push_back(r);
        impr[i][r].push_back(l);
    };
 
    for (int i = 0; i < N; i++) {
        vector<int> blocks{-1};
        for (int j = 0; j < N; j++) if (F[i][j])
            blocks.push_back(j);
        
        blocks.push_back(N);
 
        for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) {
            int l = blocks[j-1]+1, r = blocks[j]-1;
            for (int k = l; k <= r; k++) {
                add_imp(i, k, r);
                if (k != r) add_imp(i, l, k);
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sort(impl[i][j].begin(), impl[i][j].end());
            sort(impr[i][j].begin(), impr[i][j].end());
        }
    }
 
    auto upd = [&](int ni, int l, int r, int x, int cur_cost) {
        if (ni < 0 || ni >= N) return;
        int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), l) - impr[ni][r].begin();
        if (nl < sz(impr[ni][r])) {
            nl = impr[ni][r][nl];
            dp[h(ni, nl, r)] = max(dp[h(ni, nl, r)], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1));
        }
 
        int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), r) - impl[ni][l].begin() - 1;
        if (nr >= 0) {
            nr = impl[ni][l][nr];
            dp[h(ni, l, nr)] = max(dp[h(ni, l, nr)], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };
 
    // cerr << (double) clock() / CLOCKS_PER_SEC << endl;
    for (int l = 0; l < N; l++) {
        for (int r = N-1; r >= 0; r--) {
            for (int i : has[l][r]) {
                int cur_cost = get_cost(i, l, r);
                dp[h(i, l, r)] = max(dp[h(i, l, r)], cur_cost * (r - l + 1));
                // cerr << l << ' ' << r << ' ' << i << ' ' << dp[{i, l, r}] << endl;
 
                int top = i - ones[i].qry(l, r);
                int bot = i + twos[i].qry(l, r);
                upd(i, l, r, dp[h(i, l, r)], cur_cost);
                upd(top, l, r, dp[h(i, l, r)], cur_cost);
                upd(bot, l, r, dp[h(i, l, r)], cur_cost);
            }
        }
    }
 
    int ans = 0;
    for (auto& [_, v] : dp) ans = max(ans, v);
    cerr << (double) clock() / CLOCKS_PER_SEC << endl;
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284944 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 284996 KB ok
2 Correct 112 ms 284908 KB ok
3 Correct 110 ms 285016 KB ok
4 Correct 116 ms 285024 KB ok
5 Correct 111 ms 284940 KB ok
6 Correct 110 ms 284916 KB ok
7 Correct 148 ms 288792 KB ok
8 Execution timed out 4608 ms 341392 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 284996 KB ok
2 Correct 112 ms 284908 KB ok
3 Correct 112 ms 284876 KB ok
4 Correct 111 ms 284912 KB ok
5 Correct 110 ms 284908 KB ok
6 Correct 112 ms 285004 KB ok
7 Correct 113 ms 284892 KB ok
8 Correct 109 ms 284920 KB ok
9 Correct 110 ms 284884 KB ok
10 Correct 111 ms 284996 KB ok
11 Correct 112 ms 284912 KB ok
12 Correct 109 ms 284952 KB ok
13 Correct 112 ms 284896 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284944 KB ok
2 Correct 111 ms 284996 KB ok
3 Correct 112 ms 284908 KB ok
4 Correct 112 ms 284876 KB ok
5 Correct 111 ms 284912 KB ok
6 Correct 110 ms 284908 KB ok
7 Correct 112 ms 285004 KB ok
8 Correct 113 ms 284892 KB ok
9 Correct 109 ms 284920 KB ok
10 Correct 110 ms 284884 KB ok
11 Correct 111 ms 284996 KB ok
12 Correct 112 ms 284912 KB ok
13 Correct 109 ms 284952 KB ok
14 Correct 112 ms 284896 KB ok
15 Correct 109 ms 284996 KB ok
16 Correct 109 ms 284964 KB ok
17 Correct 110 ms 284940 KB ok
18 Correct 110 ms 285004 KB ok
19 Correct 111 ms 284992 KB ok
20 Correct 112 ms 284944 KB ok
21 Correct 115 ms 284984 KB ok
22 Correct 111 ms 284928 KB ok
23 Correct 108 ms 285000 KB ok
24 Correct 114 ms 284928 KB ok
25 Correct 110 ms 285012 KB ok
26 Correct 111 ms 285020 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284944 KB ok
2 Correct 111 ms 284996 KB ok
3 Correct 112 ms 284908 KB ok
4 Correct 110 ms 285016 KB ok
5 Correct 116 ms 285024 KB ok
6 Correct 112 ms 284876 KB ok
7 Correct 111 ms 284912 KB ok
8 Correct 110 ms 284908 KB ok
9 Correct 112 ms 285004 KB ok
10 Correct 113 ms 284892 KB ok
11 Correct 109 ms 284920 KB ok
12 Correct 110 ms 284884 KB ok
13 Correct 111 ms 284996 KB ok
14 Correct 112 ms 284912 KB ok
15 Correct 109 ms 284952 KB ok
16 Correct 112 ms 284896 KB ok
17 Correct 109 ms 284996 KB ok
18 Correct 109 ms 284964 KB ok
19 Correct 110 ms 284940 KB ok
20 Correct 110 ms 285004 KB ok
21 Correct 111 ms 284992 KB ok
22 Correct 112 ms 284944 KB ok
23 Correct 115 ms 284984 KB ok
24 Correct 111 ms 284928 KB ok
25 Correct 108 ms 285000 KB ok
26 Correct 114 ms 284928 KB ok
27 Correct 110 ms 285012 KB ok
28 Correct 111 ms 285020 KB ok
29 Correct 110 ms 284964 KB ok
30 Correct 112 ms 285264 KB ok
31 Correct 113 ms 285236 KB ok
32 Correct 110 ms 285156 KB ok
33 Correct 109 ms 285048 KB ok
34 Correct 128 ms 285004 KB ok
35 Correct 111 ms 285068 KB ok
36 Correct 110 ms 285000 KB ok
37 Correct 115 ms 285012 KB ok
38 Correct 115 ms 285064 KB ok
39 Correct 110 ms 285024 KB ok
40 Correct 110 ms 285256 KB ok
41 Correct 114 ms 285244 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284944 KB ok
2 Correct 111 ms 284996 KB ok
3 Correct 112 ms 284908 KB ok
4 Correct 110 ms 285016 KB ok
5 Correct 116 ms 285024 KB ok
6 Correct 112 ms 284876 KB ok
7 Correct 111 ms 284912 KB ok
8 Correct 110 ms 284908 KB ok
9 Correct 112 ms 285004 KB ok
10 Correct 113 ms 284892 KB ok
11 Correct 109 ms 284920 KB ok
12 Correct 110 ms 284884 KB ok
13 Correct 111 ms 284996 KB ok
14 Correct 112 ms 284912 KB ok
15 Correct 109 ms 284952 KB ok
16 Correct 112 ms 284896 KB ok
17 Correct 109 ms 284996 KB ok
18 Correct 109 ms 284964 KB ok
19 Correct 110 ms 284940 KB ok
20 Correct 110 ms 285004 KB ok
21 Correct 111 ms 284992 KB ok
22 Correct 112 ms 284944 KB ok
23 Correct 115 ms 284984 KB ok
24 Correct 111 ms 284928 KB ok
25 Correct 108 ms 285000 KB ok
26 Correct 114 ms 284928 KB ok
27 Correct 110 ms 285012 KB ok
28 Correct 111 ms 285020 KB ok
29 Correct 110 ms 284964 KB ok
30 Correct 112 ms 285264 KB ok
31 Correct 113 ms 285236 KB ok
32 Correct 110 ms 285156 KB ok
33 Correct 109 ms 285048 KB ok
34 Correct 128 ms 285004 KB ok
35 Correct 111 ms 285068 KB ok
36 Correct 110 ms 285000 KB ok
37 Correct 115 ms 285012 KB ok
38 Correct 115 ms 285064 KB ok
39 Correct 110 ms 285024 KB ok
40 Correct 110 ms 285256 KB ok
41 Correct 114 ms 285244 KB ok
42 Correct 507 ms 358828 KB ok
43 Correct 382 ms 356020 KB ok
44 Correct 2750 ms 362724 KB ok
45 Execution timed out 4558 ms 344628 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284944 KB ok
2 Correct 111 ms 284996 KB ok
3 Correct 112 ms 284908 KB ok
4 Correct 110 ms 285016 KB ok
5 Correct 116 ms 285024 KB ok
6 Correct 111 ms 284940 KB ok
7 Correct 110 ms 284916 KB ok
8 Correct 148 ms 288792 KB ok
9 Execution timed out 4608 ms 341392 KB Time limit exceeded
10 Halted 0 ms 0 KB -