oj.uz

Submission #840694

# Submission time Handle Problem Language Result Execution time Memory
840694 2023-08-31T15:56:47 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 601992 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(v.size())
const int M = 2e3+10, INF = 1e9+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<int, int> dp[M][M];

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]++;
            // if (i == 0) cerr << up[j] << ' ' << down[j] << endl;
            // if (i == 0) cerr << "> " << F[i][i + 1]
        }

        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[ni][nl][r] = max(dp[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[ni][l][nr] = max(dp[ni][l][nr], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };

    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[i][l][r] = max(dp[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 (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        for (auto& [_, v] : dp[i][j]) 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 198 ms 506444 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 506284 KB ok
2 Correct 195 ms 506272 KB ok
3 Correct 197 ms 506332 KB ok
4 Correct 194 ms 506404 KB ok
5 Correct 197 ms 506336 KB ok
6 Correct 199 ms 506464 KB ok
7 Correct 206 ms 509524 KB ok
8 Correct 592 ms 589416 KB ok
9 Execution timed out 4566 ms 601992 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 506284 KB ok
2 Correct 195 ms 506272 KB ok
3 Correct 203 ms 506316 KB ok
4 Correct 196 ms 506344 KB ok
5 Correct 195 ms 506316 KB ok
6 Correct 199 ms 506360 KB ok
7 Correct 193 ms 506316 KB ok
8 Correct 197 ms 506264 KB ok
9 Correct 197 ms 506336 KB ok
10 Correct 196 ms 506472 KB ok
11 Correct 197 ms 506356 KB ok
12 Correct 217 ms 506340 KB ok
13 Correct 196 ms 506284 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 506444 KB ok
2 Correct 201 ms 506284 KB ok
3 Correct 195 ms 506272 KB ok
4 Correct 203 ms 506316 KB ok
5 Correct 196 ms 506344 KB ok
6 Correct 195 ms 506316 KB ok
7 Correct 199 ms 506360 KB ok
8 Correct 193 ms 506316 KB ok
9 Correct 197 ms 506264 KB ok
10 Correct 197 ms 506336 KB ok
11 Correct 196 ms 506472 KB ok
12 Correct 197 ms 506356 KB ok
13 Correct 217 ms 506340 KB ok
14 Correct 196 ms 506284 KB ok
15 Correct 195 ms 506316 KB ok
16 Correct 197 ms 506312 KB ok
17 Correct 205 ms 506320 KB ok
18 Correct 194 ms 506316 KB ok
19 Correct 201 ms 506276 KB ok
20 Correct 195 ms 506308 KB ok
21 Correct 197 ms 506360 KB ok
22 Correct 197 ms 506304 KB ok
23 Correct 197 ms 506320 KB ok
24 Correct 197 ms 506316 KB ok
25 Correct 195 ms 506268 KB ok
26 Correct 205 ms 506332 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 506444 KB ok
2 Correct 201 ms 506284 KB ok
3 Correct 195 ms 506272 KB ok
4 Correct 197 ms 506332 KB ok
5 Correct 194 ms 506404 KB ok
6 Correct 203 ms 506316 KB ok
7 Correct 196 ms 506344 KB ok
8 Correct 195 ms 506316 KB ok
9 Correct 199 ms 506360 KB ok
10 Correct 193 ms 506316 KB ok
11 Correct 197 ms 506264 KB ok
12 Correct 197 ms 506336 KB ok
13 Correct 196 ms 506472 KB ok
14 Correct 197 ms 506356 KB ok
15 Correct 217 ms 506340 KB ok
16 Correct 196 ms 506284 KB ok
17 Correct 195 ms 506316 KB ok
18 Correct 197 ms 506312 KB ok
19 Correct 205 ms 506320 KB ok
20 Correct 194 ms 506316 KB ok
21 Correct 201 ms 506276 KB ok
22 Correct 195 ms 506308 KB ok
23 Correct 197 ms 506360 KB ok
24 Correct 197 ms 506304 KB ok
25 Correct 197 ms 506320 KB ok
26 Correct 197 ms 506316 KB ok
27 Correct 195 ms 506268 KB ok
28 Correct 205 ms 506332 KB ok
29 Correct 195 ms 506300 KB ok
30 Correct 197 ms 506544 KB ok
31 Correct 197 ms 506572 KB ok
32 Correct 206 ms 506464 KB ok
33 Correct 197 ms 506444 KB ok
34 Correct 202 ms 506436 KB ok
35 Correct 196 ms 506448 KB ok
36 Correct 196 ms 506376 KB ok
37 Correct 198 ms 506412 KB ok
38 Correct 196 ms 506452 KB ok
39 Correct 198 ms 506444 KB ok
40 Correct 197 ms 506548 KB ok
41 Correct 197 ms 506572 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 506444 KB ok
2 Correct 201 ms 506284 KB ok
3 Correct 195 ms 506272 KB ok
4 Correct 197 ms 506332 KB ok
5 Correct 194 ms 506404 KB ok
6 Correct 203 ms 506316 KB ok
7 Correct 196 ms 506344 KB ok
8 Correct 195 ms 506316 KB ok
9 Correct 199 ms 506360 KB ok
10 Correct 193 ms 506316 KB ok
11 Correct 197 ms 506264 KB ok
12 Correct 197 ms 506336 KB ok
13 Correct 196 ms 506472 KB ok
14 Correct 197 ms 506356 KB ok
15 Correct 217 ms 506340 KB ok
16 Correct 196 ms 506284 KB ok
17 Correct 195 ms 506316 KB ok
18 Correct 197 ms 506312 KB ok
19 Correct 205 ms 506320 KB ok
20 Correct 194 ms 506316 KB ok
21 Correct 201 ms 506276 KB ok
22 Correct 195 ms 506308 KB ok
23 Correct 197 ms 506360 KB ok
24 Correct 197 ms 506304 KB ok
25 Correct 197 ms 506320 KB ok
26 Correct 197 ms 506316 KB ok
27 Correct 195 ms 506268 KB ok
28 Correct 205 ms 506332 KB ok
29 Correct 195 ms 506300 KB ok
30 Correct 197 ms 506544 KB ok
31 Correct 197 ms 506572 KB ok
32 Correct 206 ms 506464 KB ok
33 Correct 197 ms 506444 KB ok
34 Correct 202 ms 506436 KB ok
35 Correct 196 ms 506448 KB ok
36 Correct 196 ms 506376 KB ok
37 Correct 198 ms 506412 KB ok
38 Correct 196 ms 506452 KB ok
39 Correct 198 ms 506444 KB ok
40 Correct 197 ms 506548 KB ok
41 Correct 197 ms 506572 KB ok
42 Correct 568 ms 582036 KB ok
43 Correct 503 ms 573760 KB ok
44 Correct 736 ms 592172 KB ok
45 Correct 735 ms 592812 KB ok
46 Correct 662 ms 587628 KB ok
47 Correct 629 ms 589584 KB ok
48 Correct 399 ms 559908 KB ok
49 Correct 447 ms 562552 KB ok
50 Correct 507 ms 569896 KB ok
51 Correct 493 ms 581576 KB ok
52 Correct 287 ms 533964 KB ok
53 Correct 237 ms 528388 KB ok
54 Correct 262 ms 533776 KB ok
55 Correct 297 ms 539928 KB ok
56 Correct 344 ms 552024 KB ok
57 Correct 597 ms 593492 KB ok
58 Correct 583 ms 593512 KB ok
59 Correct 596 ms 593516 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 506444 KB ok
2 Correct 201 ms 506284 KB ok
3 Correct 195 ms 506272 KB ok
4 Correct 197 ms 506332 KB ok
5 Correct 194 ms 506404 KB ok
6 Correct 197 ms 506336 KB ok
7 Correct 199 ms 506464 KB ok
8 Correct 206 ms 509524 KB ok
9 Correct 592 ms 589416 KB ok
10 Execution timed out 4566 ms 601992 KB Time limit exceeded
11 Halted 0 ms 0 KB -