oj.uz

Submission #840717

# Submission time Handle Problem Language Result Execution time Memory
840717 2023-08-31T16:11:20 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 374000 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];
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 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 116 ms 284916 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 284984 KB ok
2 Correct 111 ms 284944 KB ok
3 Correct 113 ms 284988 KB ok
4 Correct 158 ms 284968 KB ok
5 Correct 128 ms 284988 KB ok
6 Correct 122 ms 284936 KB ok
7 Correct 129 ms 287168 KB ok
8 Correct 508 ms 343996 KB ok
9 Execution timed out 4538 ms 374000 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 284984 KB ok
2 Correct 111 ms 284944 KB ok
3 Correct 120 ms 284896 KB ok
4 Correct 117 ms 285000 KB ok
5 Correct 111 ms 284952 KB ok
6 Correct 115 ms 284992 KB ok
7 Correct 113 ms 284896 KB ok
8 Correct 116 ms 284956 KB ok
9 Correct 112 ms 285004 KB ok
10 Correct 114 ms 284928 KB ok
11 Correct 114 ms 284988 KB ok
12 Correct 114 ms 284900 KB ok
13 Correct 112 ms 285000 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 284916 KB ok
2 Correct 115 ms 284984 KB ok
3 Correct 111 ms 284944 KB ok
4 Correct 120 ms 284896 KB ok
5 Correct 117 ms 285000 KB ok
6 Correct 111 ms 284952 KB ok
7 Correct 115 ms 284992 KB ok
8 Correct 113 ms 284896 KB ok
9 Correct 116 ms 284956 KB ok
10 Correct 112 ms 285004 KB ok
11 Correct 114 ms 284928 KB ok
12 Correct 114 ms 284988 KB ok
13 Correct 114 ms 284900 KB ok
14 Correct 112 ms 285000 KB ok
15 Correct 112 ms 284960 KB ok
16 Correct 112 ms 285004 KB ok
17 Correct 117 ms 284948 KB ok
18 Correct 113 ms 285004 KB ok
19 Correct 112 ms 284980 KB ok
20 Correct 114 ms 284876 KB ok
21 Correct 109 ms 284904 KB ok
22 Correct 112 ms 285004 KB ok
23 Correct 137 ms 284916 KB ok
24 Correct 110 ms 285004 KB ok
25 Correct 111 ms 285004 KB ok
26 Correct 116 ms 284952 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 284916 KB ok
2 Correct 115 ms 284984 KB ok
3 Correct 111 ms 284944 KB ok
4 Correct 113 ms 284988 KB ok
5 Correct 158 ms 284968 KB ok
6 Correct 120 ms 284896 KB ok
7 Correct 117 ms 285000 KB ok
8 Correct 111 ms 284952 KB ok
9 Correct 115 ms 284992 KB ok
10 Correct 113 ms 284896 KB ok
11 Correct 116 ms 284956 KB ok
12 Correct 112 ms 285004 KB ok
13 Correct 114 ms 284928 KB ok
14 Correct 114 ms 284988 KB ok
15 Correct 114 ms 284900 KB ok
16 Correct 112 ms 285000 KB ok
17 Correct 112 ms 284960 KB ok
18 Correct 112 ms 285004 KB ok
19 Correct 117 ms 284948 KB ok
20 Correct 113 ms 285004 KB ok
21 Correct 112 ms 284980 KB ok
22 Correct 114 ms 284876 KB ok
23 Correct 109 ms 284904 KB ok
24 Correct 112 ms 285004 KB ok
25 Correct 137 ms 284916 KB ok
26 Correct 110 ms 285004 KB ok
27 Correct 111 ms 285004 KB ok
28 Correct 116 ms 284952 KB ok
29 Correct 114 ms 284900 KB ok
30 Correct 114 ms 285128 KB ok
31 Correct 111 ms 285124 KB ok
32 Correct 113 ms 285112 KB ok
33 Correct 109 ms 285004 KB ok
34 Correct 110 ms 284984 KB ok
35 Correct 113 ms 285020 KB ok
36 Correct 114 ms 285040 KB ok
37 Correct 112 ms 285136 KB ok
38 Correct 116 ms 285004 KB ok
39 Correct 114 ms 285004 KB ok
40 Correct 112 ms 285140 KB ok
41 Correct 116 ms 285192 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 284916 KB ok
2 Correct 115 ms 284984 KB ok
3 Correct 111 ms 284944 KB ok
4 Correct 113 ms 284988 KB ok
5 Correct 158 ms 284968 KB ok
6 Correct 120 ms 284896 KB ok
7 Correct 117 ms 285000 KB ok
8 Correct 111 ms 284952 KB ok
9 Correct 115 ms 284992 KB ok
10 Correct 113 ms 284896 KB ok
11 Correct 116 ms 284956 KB ok
12 Correct 112 ms 285004 KB ok
13 Correct 114 ms 284928 KB ok
14 Correct 114 ms 284988 KB ok
15 Correct 114 ms 284900 KB ok
16 Correct 112 ms 285000 KB ok
17 Correct 112 ms 284960 KB ok
18 Correct 112 ms 285004 KB ok
19 Correct 117 ms 284948 KB ok
20 Correct 113 ms 285004 KB ok
21 Correct 112 ms 284980 KB ok
22 Correct 114 ms 284876 KB ok
23 Correct 109 ms 284904 KB ok
24 Correct 112 ms 285004 KB ok
25 Correct 137 ms 284916 KB ok
26 Correct 110 ms 285004 KB ok
27 Correct 111 ms 285004 KB ok
28 Correct 116 ms 284952 KB ok
29 Correct 114 ms 284900 KB ok
30 Correct 114 ms 285128 KB ok
31 Correct 111 ms 285124 KB ok
32 Correct 113 ms 285112 KB ok
33 Correct 109 ms 285004 KB ok
34 Correct 110 ms 284984 KB ok
35 Correct 113 ms 285020 KB ok
36 Correct 114 ms 285040 KB ok
37 Correct 112 ms 285136 KB ok
38 Correct 116 ms 285004 KB ok
39 Correct 114 ms 285004 KB ok
40 Correct 112 ms 285140 KB ok
41 Correct 116 ms 285192 KB ok
42 Correct 526 ms 341124 KB ok
43 Correct 398 ms 338272 KB ok
44 Correct 671 ms 346584 KB ok
45 Correct 679 ms 347100 KB ok
46 Correct 601 ms 343956 KB ok
47 Correct 507 ms 344244 KB ok
48 Correct 306 ms 326036 KB ok
49 Correct 307 ms 327516 KB ok
50 Correct 397 ms 329680 KB ok
51 Correct 418 ms 341404 KB ok
52 Correct 172 ms 309212 KB ok
53 Correct 162 ms 305808 KB ok
54 Correct 172 ms 309212 KB ok
55 Correct 194 ms 313332 KB ok
56 Correct 242 ms 321808 KB ok
57 Correct 509 ms 347800 KB ok
58 Correct 514 ms 347644 KB ok
59 Correct 548 ms 347572 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 284916 KB ok
2 Correct 115 ms 284984 KB ok
3 Correct 111 ms 284944 KB ok
4 Correct 113 ms 284988 KB ok
5 Correct 158 ms 284968 KB ok
6 Correct 128 ms 284988 KB ok
7 Correct 122 ms 284936 KB ok
8 Correct 129 ms 287168 KB ok
9 Correct 508 ms 343996 KB ok
10 Execution timed out 4538 ms 374000 KB Time limit exceeded
11 Halted 0 ms 0 KB -