oj.uz

Submission #840736

# Submission time Handle Problem Language Result Execution time Memory
840736 2023-08-31T16:26:13 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 1305936 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
#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);
}
 
int store_up[M][M], store_down[M][M];
vector<int> impl[M][M];
vector<int> impr[M][M];
vector<int> has[M][M];
unordered_map<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 j = 0; j < N; j++) {
        int one = 0;
        for (int i = 0; i < N; i++) {
            one = F[i][j] ? 0 : one + 1;
            store_up[i][j] = one;
        }

        int two = 0;
        for (int i = N-1; i >= 0; i--) {
            two = F[i][j] ? 0 : two + 1;
            store_down[i][j] = two ;
        }
    }

    for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            up[j] = store_up[i][j], down[j] = store_down[i][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);
                int store = 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, store, cur_cost);
                upd(top, l, r, store, cur_cost);
                upd(bot, l, r, store, 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 135 ms 284952 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 285008 KB ok
2 Correct 125 ms 284932 KB ok
3 Correct 118 ms 285104 KB ok
4 Correct 112 ms 285112 KB ok
5 Correct 136 ms 284912 KB ok
6 Correct 117 ms 284916 KB ok
7 Correct 117 ms 288064 KB ok
8 Correct 366 ms 349988 KB ok
9 Execution timed out 4599 ms 1305936 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 285008 KB ok
2 Correct 125 ms 284932 KB ok
3 Correct 114 ms 284972 KB ok
4 Correct 114 ms 284940 KB ok
5 Correct 121 ms 284912 KB ok
6 Correct 118 ms 285032 KB ok
7 Correct 113 ms 285040 KB ok
8 Correct 114 ms 284920 KB ok
9 Correct 126 ms 284936 KB ok
10 Correct 127 ms 285016 KB ok
11 Correct 115 ms 284928 KB ok
12 Correct 113 ms 285024 KB ok
13 Correct 136 ms 285032 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 284952 KB ok
2 Correct 117 ms 285008 KB ok
3 Correct 125 ms 284932 KB ok
4 Correct 114 ms 284972 KB ok
5 Correct 114 ms 284940 KB ok
6 Correct 121 ms 284912 KB ok
7 Correct 118 ms 285032 KB ok
8 Correct 113 ms 285040 KB ok
9 Correct 114 ms 284920 KB ok
10 Correct 126 ms 284936 KB ok
11 Correct 127 ms 285016 KB ok
12 Correct 115 ms 284928 KB ok
13 Correct 113 ms 285024 KB ok
14 Correct 136 ms 285032 KB ok
15 Correct 110 ms 285060 KB ok
16 Correct 114 ms 284996 KB ok
17 Correct 112 ms 285056 KB ok
18 Correct 125 ms 285064 KB ok
19 Correct 112 ms 285032 KB ok
20 Correct 120 ms 284948 KB ok
21 Correct 121 ms 285016 KB ok
22 Correct 113 ms 284968 KB ok
23 Correct 118 ms 284996 KB ok
24 Correct 113 ms 285028 KB ok
25 Correct 111 ms 284984 KB ok
26 Correct 113 ms 284980 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 284952 KB ok
2 Correct 117 ms 285008 KB ok
3 Correct 125 ms 284932 KB ok
4 Correct 118 ms 285104 KB ok
5 Correct 112 ms 285112 KB ok
6 Correct 114 ms 284972 KB ok
7 Correct 114 ms 284940 KB ok
8 Correct 121 ms 284912 KB ok
9 Correct 118 ms 285032 KB ok
10 Correct 113 ms 285040 KB ok
11 Correct 114 ms 284920 KB ok
12 Correct 126 ms 284936 KB ok
13 Correct 127 ms 285016 KB ok
14 Correct 115 ms 284928 KB ok
15 Correct 113 ms 285024 KB ok
16 Correct 136 ms 285032 KB ok
17 Correct 110 ms 285060 KB ok
18 Correct 114 ms 284996 KB ok
19 Correct 112 ms 285056 KB ok
20 Correct 125 ms 285064 KB ok
21 Correct 112 ms 285032 KB ok
22 Correct 120 ms 284948 KB ok
23 Correct 121 ms 285016 KB ok
24 Correct 113 ms 284968 KB ok
25 Correct 118 ms 284996 KB ok
26 Correct 113 ms 285028 KB ok
27 Correct 111 ms 284984 KB ok
28 Correct 113 ms 284980 KB ok
29 Correct 126 ms 285040 KB ok
30 Correct 122 ms 285392 KB ok
31 Correct 113 ms 285388 KB ok
32 Correct 117 ms 285256 KB ok
33 Correct 118 ms 285324 KB ok
34 Correct 115 ms 285264 KB ok
35 Correct 112 ms 285268 KB ok
36 Correct 117 ms 285252 KB ok
37 Correct 123 ms 285296 KB ok
38 Correct 135 ms 285224 KB ok
39 Correct 113 ms 285284 KB ok
40 Correct 113 ms 285364 KB ok
41 Correct 117 ms 285376 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 284952 KB ok
2 Correct 117 ms 285008 KB ok
3 Correct 125 ms 284932 KB ok
4 Correct 118 ms 285104 KB ok
5 Correct 112 ms 285112 KB ok
6 Correct 114 ms 284972 KB ok
7 Correct 114 ms 284940 KB ok
8 Correct 121 ms 284912 KB ok
9 Correct 118 ms 285032 KB ok
10 Correct 113 ms 285040 KB ok
11 Correct 114 ms 284920 KB ok
12 Correct 126 ms 284936 KB ok
13 Correct 127 ms 285016 KB ok
14 Correct 115 ms 284928 KB ok
15 Correct 113 ms 285024 KB ok
16 Correct 136 ms 285032 KB ok
17 Correct 110 ms 285060 KB ok
18 Correct 114 ms 284996 KB ok
19 Correct 112 ms 285056 KB ok
20 Correct 125 ms 285064 KB ok
21 Correct 112 ms 285032 KB ok
22 Correct 120 ms 284948 KB ok
23 Correct 121 ms 285016 KB ok
24 Correct 113 ms 284968 KB ok
25 Correct 118 ms 284996 KB ok
26 Correct 113 ms 285028 KB ok
27 Correct 111 ms 284984 KB ok
28 Correct 113 ms 284980 KB ok
29 Correct 126 ms 285040 KB ok
30 Correct 122 ms 285392 KB ok
31 Correct 113 ms 285388 KB ok
32 Correct 117 ms 285256 KB ok
33 Correct 118 ms 285324 KB ok
34 Correct 115 ms 285264 KB ok
35 Correct 112 ms 285268 KB ok
36 Correct 117 ms 285252 KB ok
37 Correct 123 ms 285296 KB ok
38 Correct 135 ms 285224 KB ok
39 Correct 113 ms 285284 KB ok
40 Correct 113 ms 285364 KB ok
41 Correct 117 ms 285376 KB ok
42 Correct 555 ms 347072 KB ok
43 Correct 407 ms 344292 KB ok
44 Correct 647 ms 352692 KB ok
45 Correct 619 ms 353096 KB ok
46 Correct 574 ms 349980 KB ok
47 Correct 425 ms 350296 KB ok
48 Correct 276 ms 332012 KB ok
49 Correct 279 ms 333444 KB ok
50 Correct 331 ms 335700 KB ok
51 Correct 402 ms 347292 KB ok
52 Correct 172 ms 315204 KB ok
53 Correct 178 ms 311732 KB ok
54 Correct 170 ms 315224 KB ok
55 Correct 202 ms 319392 KB ok
56 Correct 238 ms 327832 KB ok
57 Correct 423 ms 353720 KB ok
58 Correct 497 ms 353616 KB ok
59 Correct 449 ms 353568 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 284952 KB ok
2 Correct 117 ms 285008 KB ok
3 Correct 125 ms 284932 KB ok
4 Correct 118 ms 285104 KB ok
5 Correct 112 ms 285112 KB ok
6 Correct 136 ms 284912 KB ok
7 Correct 117 ms 284916 KB ok
8 Correct 117 ms 288064 KB ok
9 Correct 366 ms 349988 KB ok
10 Execution timed out 4599 ms 1305936 KB Time limit exceeded
11 Halted 0 ms 0 KB -