oj.uz

답안 #963803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963803 2024-04-15T17:18:59 Z tutis 축구 경기장 (IOI23_soccer) C++17
70 / 100
 4500 ms 123432 KB 
//#include "soccer.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int biggest_stadium(int N, std::vector<std::vector<int>> C) {
    vector<vector<int>> S(N);
    auto fS = [&](int x, int y) {
        if (x < 0 || y < 0) {
            return 0;
        }
        if (x >= N) {
            x = N - 1;
        }
        if (y >= N) {
            y = N - 1;
        }
        return S[x][y];
    };
    auto sm = [&](int x1, int x2, int y1, int y2) -> int {
        return fS(x2, y2) - fS(x1 - 1, y2) - fS(x2, y1 - 1) + fS(x1 - 1, y1 - 1);
    };
    for (int i = 0; i < N; i++) {
        S[i] = vector<int>(N);
        for (int j = 0; j < N; j++) {
            S[i][j] = C[i][j];
            S[i][j] += fS(i - 1, j) + fS(i, j - 1) - fS(i - 1, j - 1);
        }
    }
    vector<vector<int>> on(N);
    for (int x = 0; x < N; x++) {
        on[x] = vector<int>(N);
        int lst = N;
        for (int y = N - 1; y >= 0; y--) {
            if (C[x][y] == 1) {
                lst = y;
            }
            on[x][y] = lst;
        }
    }
    auto ones = [&](int x, int y0, int y1) -> vector<int> {
        if (y0 > y1) {
            return {};
        }
        vector<int> p;
        while (y0 <= y1) {
            int nxt = on[x][y0];
            if (nxt >= y1 + 1) {
                break;
            }
            p.push_back(nxt);
            y0 = nxt + 1;
        }
        p.push_back(y1 + 1);
        return p;
    };
    int best = 0;
    vector<pair<pair<int, int>, pair<int, int>>> V;
    function<void(int, int, int, int)> dfs = [&](int x1, int x2, int y1, int y2) -> void {
        if (y1 > y2) {
            return;
        }
        if (x2 != N - 1 && sm(x2 + 1, x2 + 1, y1, y2) == 0) {
            return;
        }
        if (x1 == 0) {
            V.push_back({{x1, x2},
                         {y1, y2}});
            return;
        }
        if (sm(x1 - 1, x1 - 1, y1, y2) != 0) {
            V.push_back({{x1, x2},
                         {y1, y2}});
        }
        if (sm(x1 - 1, x1 - 1, y1, y2) == 0) {
            int lo = 0;
            int hi = x1 - 1;
            while (lo < hi) {
                int m = (lo + hi) / 2;
                if (sm(m, x1 - 1, y1, y2) == 0) {
                    hi = m;
                } else {
                    lo = m + 1;
                }
            }
            dfs(lo, x2, y1, y2);
            return;
        }
        int lst = y1 - 1;
        for (int y: ones(x1 - 1, y1, y2)) {
            dfs(x1 - 1, x2, lst + 1, y - 1);
            lst = y;
        }
    };
    for (int x = 0; x < N; x++) {
        int lst = -1;
        for (int y = 0; y <= N; y++) {
            if (y == N || C[x][y] == 1) {
                if (lst + 1 > y - 1) {
                    lst = y;
                    continue;
                }
                if (x != N - 1 && sm(x + 1, x + 1, lst + 1, y - 1) == 0) {
                    lst = y;
                    continue;
                }
                dfs(x, x, lst + 1, y - 1);
                lst = y;
            }
        }
    }
    sort(V.begin(), V.end(),
         [&](pair<pair<int, int>, pair<int, int>> a, pair<pair<int, int>, pair<int, int>> b) {
             return a.second.second - a.second.first > b.second.second - b.second.first;
         });
    map<pair<pair<int, int>, pair<int, int>>, int> M;
    auto check = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        if (y0 > y1) {
            return;
        }
        int lo = 0;
        int hi = x0;
        while (lo < hi) {
            int m = (lo + hi) / 2;
            if (sm(m, x0 - 1, y0, y1) == 0) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        area += (y1 - y0 + 1) * (x0 - lo);
        x0 = lo;
        lo = x1;
        hi = N - 1;
        while (lo < hi) {
            int m = (lo + hi + 1) / 2;
            if (sm(x1 + 1, m, y0, y1) == 0) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }

        area += (y1 - y0 + 1) * (lo - x1);
        x1 = lo;
        M[{{x0, x1},
           {y0, y1}}] = max(M[{{x0, x1},
                               {y0, y1}}],
                            area);
    };
    auto expL = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        if (y0 > y1) {
            return;
        }
        int lst = y0 - 1;
        for (int y: ones(x0 - 1, y0, y1)) {
            check({{x0 - 1,  x1},
                   {lst + 1, y - 1}}, area + (y - 1) - (lst + 1) + 1);
            lst = y;
        }
    };
    auto expR = [&](pair<pair<int, int>, pair<int, int>> i, int area) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        if (y0 > y1) {
            return;
        }
        int lst = y0 - 1;
        for (int y: ones(x1 + 1, y0, y1)) {
            check({{x0,      x1 + 1},
                   {lst + 1, y - 1}}, area + (y - 1) - (lst + 1) + 1);
            lst = y;
        }
    };
    for (auto i: V) {
        auto [xp, yp] = i;
        auto [x0, x1] = xp;
        auto [y0, y1] = yp;
        int dp = (x1 - x0 + 1) * (y1 - y0 + 1);
        if (M.count(i)) {
            dp = M[i];
        }
        if (dp + (y1 - y0) * (x0 + (N - x1 - 1)) <= best) {
            continue;
        }
        int ans = dp;
        best = max(best, ans);
        if (x0 != 0) {
            expL(i, ans);
        }
        if (x1 != N - 1) {
            expR(i, ans);
        }
    }

    return best;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 436 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 16 ms 4692 KB ok
9 Correct 266 ms 67384 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 684 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 684 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 432 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 348 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 684 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 432 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 436 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 348 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 684 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 432 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 436 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 135 ms 8232 KB ok
43 Correct 137 ms 8636 KB ok
44 Correct 46 ms 5660 KB ok
45 Correct 40 ms 5388 KB ok
46 Correct 107 ms 7328 KB ok
47 Correct 16 ms 4740 KB ok
48 Correct 18 ms 4736 KB ok
49 Correct 17 ms 4700 KB ok
50 Correct 51 ms 4800 KB ok
51 Correct 31 ms 5328 KB ok
52 Correct 18 ms 4956 KB ok
53 Correct 18 ms 4696 KB ok
54 Correct 20 ms 4736 KB ok
55 Correct 18 ms 4876 KB ok
56 Correct 17 ms 4696 KB ok
57 Correct 121 ms 9884 KB ok
58 Correct 120 ms 10428 KB ok
59 Correct 124 ms 11028 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 1 ms 436 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 604 KB ok
9 Correct 16 ms 4692 KB ok
10 Correct 266 ms 67384 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 684 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 432 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 436 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 1 ms 348 KB ok
44 Correct 1 ms 348 KB ok
45 Correct 0 ms 348 KB ok
46 Correct 1 ms 348 KB ok
47 Correct 135 ms 8232 KB ok
48 Correct 137 ms 8636 KB ok
49 Correct 46 ms 5660 KB ok
50 Correct 40 ms 5388 KB ok
51 Correct 107 ms 7328 KB ok
52 Correct 16 ms 4740 KB ok
53 Correct 18 ms 4736 KB ok
54 Correct 17 ms 4700 KB ok
55 Correct 51 ms 4800 KB ok
56 Correct 31 ms 5328 KB ok
57 Correct 18 ms 4956 KB ok
58 Correct 18 ms 4696 KB ok
59 Correct 20 ms 4736 KB ok
60 Correct 18 ms 4876 KB ok
61 Correct 17 ms 4696 KB ok
62 Correct 121 ms 9884 KB ok
63 Correct 120 ms 10428 KB ok
64 Correct 124 ms 11028 KB ok
65 Execution timed out 4574 ms 123432 KB Time limit exceeded
66 Halted 0 ms 0 KB -