oj.uz

답안 #840696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840696 2023-08-31T15:58:10 Z PurpleCrayon 축구 경기장 (IOI23_soccer) C++17
64 / 100
 4500 ms 577256 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];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 474652 KB ok

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 474756 KB ok
2 Correct 175 ms 474632 KB ok
3 Correct 177 ms 474684 KB ok
4 Correct 181 ms 474700 KB ok
5 Correct 180 ms 474716 KB ok
6 Correct 174 ms 474748 KB ok
7 Correct 182 ms 477016 KB ok
8 Correct 547 ms 536092 KB ok
9 Execution timed out 4579 ms 577256 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 474756 KB ok
2 Correct 175 ms 474632 KB ok
3 Correct 184 ms 474640 KB ok
4 Correct 178 ms 474744 KB ok
5 Correct 179 ms 474704 KB ok
6 Correct 179 ms 474708 KB ok
7 Correct 174 ms 474700 KB ok
8 Correct 179 ms 474660 KB ok
9 Correct 178 ms 474672 KB ok
10 Correct 176 ms 474700 KB ok
11 Correct 177 ms 474696 KB ok
12 Correct 178 ms 474636 KB ok
13 Correct 175 ms 474668 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 474652 KB ok
2 Correct 180 ms 474756 KB ok
3 Correct 175 ms 474632 KB ok
4 Correct 184 ms 474640 KB ok
5 Correct 178 ms 474744 KB ok
6 Correct 179 ms 474704 KB ok
7 Correct 179 ms 474708 KB ok
8 Correct 174 ms 474700 KB ok
9 Correct 179 ms 474660 KB ok
10 Correct 178 ms 474672 KB ok
11 Correct 176 ms 474700 KB ok
12 Correct 177 ms 474696 KB ok
13 Correct 178 ms 474636 KB ok
14 Correct 175 ms 474668 KB ok
15 Correct 176 ms 474648 KB ok
16 Correct 180 ms 474700 KB ok
17 Correct 183 ms 474848 KB ok
18 Correct 177 ms 474740 KB ok
19 Correct 177 ms 474760 KB ok
20 Correct 175 ms 474712 KB ok
21 Correct 180 ms 474668 KB ok
22 Correct 184 ms 474752 KB ok
23 Correct 178 ms 474688 KB ok
24 Correct 181 ms 474664 KB ok
25 Correct 178 ms 474712 KB ok
26 Correct 184 ms 474700 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 474652 KB ok
2 Correct 180 ms 474756 KB ok
3 Correct 175 ms 474632 KB ok
4 Correct 177 ms 474684 KB ok
5 Correct 181 ms 474700 KB ok
6 Correct 184 ms 474640 KB ok
7 Correct 178 ms 474744 KB ok
8 Correct 179 ms 474704 KB ok
9 Correct 179 ms 474708 KB ok
10 Correct 174 ms 474700 KB ok
11 Correct 179 ms 474660 KB ok
12 Correct 178 ms 474672 KB ok
13 Correct 176 ms 474700 KB ok
14 Correct 177 ms 474696 KB ok
15 Correct 178 ms 474636 KB ok
16 Correct 175 ms 474668 KB ok
17 Correct 176 ms 474648 KB ok
18 Correct 180 ms 474700 KB ok
19 Correct 183 ms 474848 KB ok
20 Correct 177 ms 474740 KB ok
21 Correct 177 ms 474760 KB ok
22 Correct 175 ms 474712 KB ok
23 Correct 180 ms 474668 KB ok
24 Correct 184 ms 474752 KB ok
25 Correct 178 ms 474688 KB ok
26 Correct 181 ms 474664 KB ok
27 Correct 178 ms 474712 KB ok
28 Correct 184 ms 474700 KB ok
29 Correct 199 ms 474732 KB ok
30 Correct 197 ms 474944 KB ok
31 Correct 179 ms 474924 KB ok
32 Correct 178 ms 474860 KB ok
33 Correct 179 ms 474768 KB ok
34 Correct 179 ms 474812 KB ok
35 Correct 177 ms 474848 KB ok
36 Correct 179 ms 474768 KB ok
37 Correct 185 ms 474828 KB ok
38 Correct 177 ms 474808 KB ok
39 Correct 179 ms 474792 KB ok
40 Correct 179 ms 474804 KB ok
41 Correct 179 ms 474888 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 474652 KB ok
2 Correct 180 ms 474756 KB ok
3 Correct 175 ms 474632 KB ok
4 Correct 177 ms 474684 KB ok
5 Correct 181 ms 474700 KB ok
6 Correct 184 ms 474640 KB ok
7 Correct 178 ms 474744 KB ok
8 Correct 179 ms 474704 KB ok
9 Correct 179 ms 474708 KB ok
10 Correct 174 ms 474700 KB ok
11 Correct 179 ms 474660 KB ok
12 Correct 178 ms 474672 KB ok
13 Correct 176 ms 474700 KB ok
14 Correct 177 ms 474696 KB ok
15 Correct 178 ms 474636 KB ok
16 Correct 175 ms 474668 KB ok
17 Correct 176 ms 474648 KB ok
18 Correct 180 ms 474700 KB ok
19 Correct 183 ms 474848 KB ok
20 Correct 177 ms 474740 KB ok
21 Correct 177 ms 474760 KB ok
22 Correct 175 ms 474712 KB ok
23 Correct 180 ms 474668 KB ok
24 Correct 184 ms 474752 KB ok
25 Correct 178 ms 474688 KB ok
26 Correct 181 ms 474664 KB ok
27 Correct 178 ms 474712 KB ok
28 Correct 184 ms 474700 KB ok
29 Correct 199 ms 474732 KB ok
30 Correct 197 ms 474944 KB ok
31 Correct 179 ms 474924 KB ok
32 Correct 178 ms 474860 KB ok
33 Correct 179 ms 474768 KB ok
34 Correct 179 ms 474812 KB ok
35 Correct 177 ms 474848 KB ok
36 Correct 179 ms 474768 KB ok
37 Correct 185 ms 474828 KB ok
38 Correct 177 ms 474808 KB ok
39 Correct 179 ms 474792 KB ok
40 Correct 179 ms 474804 KB ok
41 Correct 179 ms 474888 KB ok
42 Correct 508 ms 531572 KB ok
43 Correct 439 ms 525504 KB ok
44 Correct 706 ms 538580 KB ok
45 Correct 758 ms 539024 KB ok
46 Correct 587 ms 535380 KB ok
47 Correct 573 ms 536268 KB ok
48 Correct 383 ms 516996 KB ok
49 Correct 393 ms 518744 KB ok
50 Correct 458 ms 521616 KB ok
51 Correct 468 ms 531256 KB ok
52 Correct 241 ms 499472 KB ok
53 Correct 216 ms 495652 KB ok
54 Correct 252 ms 499388 KB ok
55 Correct 281 ms 503508 KB ok
56 Correct 308 ms 511508 KB ok
57 Correct 568 ms 539776 KB ok
58 Correct 584 ms 539688 KB ok
59 Correct 547 ms 539468 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 474652 KB ok
2 Correct 180 ms 474756 KB ok
3 Correct 175 ms 474632 KB ok
4 Correct 177 ms 474684 KB ok
5 Correct 181 ms 474700 KB ok
6 Correct 180 ms 474716 KB ok
7 Correct 174 ms 474748 KB ok
8 Correct 182 ms 477016 KB ok
9 Correct 547 ms 536092 KB ok
10 Execution timed out 4579 ms 577256 KB Time limit exceeded
11 Halted 0 ms 0 KB -