oj.uz

Submission #840685

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

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

int check_full(int N, std::vector<std::vector<int>> F) {
    vector<int> one, two;
    vector<pair<int, int>> ranges;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int mn = N, mx = -1, cnt = 0;
        for (int j = 0; j < N; j++) {
            if (!F[i][j]) {
                mn = min(mn, j);
                mx = max(mx, j);
                cnt++;
                ans++;
            }
        }

        if (cnt && cnt != mx - mn + 1) return 0;
        one.push_back(mn);
        two.push_back(mx);
        if (cnt) ranges.push_back({mn, mx});
    }

    auto contains = [&](pair<int, int> p1, pair<int, int> p2) {
        return p1.first <= p2.first && p2.second <= p1.second;
    };

    for (auto p1 : ranges) {
        for (auto p2 : ranges) {
            if (!contains(p1, p2) && !contains(p2, p1))
                return 0;
        }
    }

    int m1 = min_element(one.begin(), one.end()) - one.begin();
    for (int i = m1; i > 0; i--) if (one[i] > one[i-1]) return 0;
    for (int i = m1; i < N-1; i++) if (one[i] > one[i+1]) return 0;
    int m2 = max_element(two.begin(), two.end()) - two.begin();
    for (int i = m2; i > 0; i--) if (two[i] < two[i-1]) return 0;
    for (int i = m2; i < N-1; i++) if (two[i] < two[i+1]) return 0;
    return ans;
}

int run_subtask(int N, std::vector<std::vector<int>> F) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                return N * N - min(i + 1, N - i) * min(j + 1, N - j);
            }
        }
    }
    assert(false);
}

int get_cost(int i, int l, int r) {
    // int one = i + 1, two = N - i;
    // for (int i = l; i <= r; i++) one = min(one, up[i]);
    // for (int i = l; i <= r; i++) two = min(two, down[i]);
    // return max(0, one + two - 1);
    // cerr << l << ' ' << r << endl;
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}

#define N MAXN
vector<int> impl[N][N];
vector<int> impr[N][N];
vector<int> has[N][N];
#undef N
map<ar<int, 3>, int> dp;

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    int test = check_full(N, F);
    if (test) return test;

    int cnt_fill = 0;
    for (auto v : F) for (auto x : v) cnt_fill += x;
    if (cnt_fill == 1) {
        return run_subtask(N, 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);
        // vector<vector<int>> dp(N, vector<int>(N, -INF));
        // for (int l = 0; l < N; l++) {
        //     for (int r = N-1; r >= l; r--) {
        //         dp[l][r] = get_cost(l, r) * (r - l + 1);
        //     }
        // }

        // for (int l = 0; l < N; l++) {
        //     for (int r = N-1; r > l; r--) if (dp[l][r] >= 0) {
        //         // if (i == 2) cerr << l << ' ' << r << ' ' << dp[l][r] << endl;
        //         // if (i == 2 && l == 0 && r == 4) cerr << ">> " << get_cost(l + 1, r) << ' ' << get_cost(l, r) << endl;
        //         dp[l+1][r] = max(dp[l+1][r], (get_cost(l + 1, r) - get_cost(l, r)) * (r - l) + dp[l][r]);
        //         dp[l][r-1] = max(dp[l][r-1], (get_cost(l, r - 1) - get_cost(l, r)) * (r - l) + dp[l][r]);
        //     }
        // }

        // for (int i = 0; i < N; i++)
        //     for (int j = 0; j < N; j++) {
        //         ans = max(ans, dp[i][j]);
        //     }
    }

    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);
                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, dp[{i, l, r}], cur_cost);
                upd(top, l, r, dp[{i, l, r}], cur_cost);
                upd(bot, l, r, dp[{i, l, r}], cur_cost);
            }
        }
    }

    int ans = 0;
    for (auto& [_, v] : dp) ans = max(ans, v);
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284948 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 285004 KB ok
2 Correct 110 ms 284944 KB ok
3 Correct 110 ms 285004 KB ok
4 Correct 110 ms 284896 KB ok
5 Correct 110 ms 284968 KB ok
6 Correct 110 ms 284888 KB ok
7 Correct 111 ms 285108 KB ok
8 Correct 123 ms 287952 KB ok
9 Correct 358 ms 332244 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 285004 KB ok
2 Correct 110 ms 284944 KB ok
3 Correct 108 ms 284928 KB ok
4 Correct 108 ms 285000 KB ok
5 Correct 108 ms 284876 KB ok
6 Correct 109 ms 285132 KB ok
7 Correct 113 ms 285044 KB ok
8 Correct 109 ms 284876 KB ok
9 Correct 111 ms 285004 KB ok
10 Correct 113 ms 285256 KB ok
11 Correct 111 ms 284876 KB ok
12 Correct 111 ms 284896 KB ok
13 Correct 123 ms 284996 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284948 KB ok
2 Correct 110 ms 285004 KB ok
3 Correct 110 ms 284944 KB ok
4 Correct 108 ms 284928 KB ok
5 Correct 108 ms 285000 KB ok
6 Correct 108 ms 284876 KB ok
7 Correct 109 ms 285132 KB ok
8 Correct 113 ms 285044 KB ok
9 Correct 109 ms 284876 KB ok
10 Correct 111 ms 285004 KB ok
11 Correct 113 ms 285256 KB ok
12 Correct 111 ms 284876 KB ok
13 Correct 111 ms 284896 KB ok
14 Correct 123 ms 284996 KB ok
15 Correct 110 ms 285004 KB ok
16 Correct 109 ms 284976 KB ok
17 Correct 111 ms 284952 KB ok
18 Correct 110 ms 284928 KB ok
19 Correct 119 ms 284948 KB ok
20 Correct 111 ms 284960 KB ok
21 Correct 115 ms 284964 KB ok
22 Correct 109 ms 284944 KB ok
23 Correct 111 ms 284948 KB ok
24 Correct 112 ms 285012 KB ok
25 Correct 109 ms 284984 KB ok
26 Correct 110 ms 285000 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284948 KB ok
2 Correct 110 ms 285004 KB ok
3 Correct 110 ms 284944 KB ok
4 Correct 110 ms 285004 KB ok
5 Correct 110 ms 284896 KB ok
6 Correct 108 ms 284928 KB ok
7 Correct 108 ms 285000 KB ok
8 Correct 108 ms 284876 KB ok
9 Correct 109 ms 285132 KB ok
10 Correct 113 ms 285044 KB ok
11 Correct 109 ms 284876 KB ok
12 Correct 111 ms 285004 KB ok
13 Correct 113 ms 285256 KB ok
14 Correct 111 ms 284876 KB ok
15 Correct 111 ms 284896 KB ok
16 Correct 123 ms 284996 KB ok
17 Correct 110 ms 285004 KB ok
18 Correct 109 ms 284976 KB ok
19 Correct 111 ms 284952 KB ok
20 Correct 110 ms 284928 KB ok
21 Correct 119 ms 284948 KB ok
22 Correct 111 ms 284960 KB ok
23 Correct 115 ms 284964 KB ok
24 Correct 109 ms 284944 KB ok
25 Correct 111 ms 284948 KB ok
26 Correct 112 ms 285012 KB ok
27 Correct 109 ms 284984 KB ok
28 Correct 110 ms 285000 KB ok
29 Correct 109 ms 285096 KB ok
30 Correct 113 ms 285132 KB ok
31 Correct 112 ms 285164 KB ok
32 Correct 110 ms 285004 KB ok
33 Correct 108 ms 285004 KB ok
34 Correct 108 ms 285004 KB ok
35 Correct 111 ms 285008 KB ok
36 Correct 109 ms 285004 KB ok
37 Correct 110 ms 284984 KB ok
38 Correct 110 ms 285056 KB ok
39 Correct 126 ms 285132 KB ok
40 Correct 111 ms 285068 KB ok
41 Correct 113 ms 285132 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284948 KB ok
2 Correct 110 ms 285004 KB ok
3 Correct 110 ms 284944 KB ok
4 Correct 110 ms 285004 KB ok
5 Correct 110 ms 284896 KB ok
6 Correct 108 ms 284928 KB ok
7 Correct 108 ms 285000 KB ok
8 Correct 108 ms 284876 KB ok
9 Correct 109 ms 285132 KB ok
10 Correct 113 ms 285044 KB ok
11 Correct 109 ms 284876 KB ok
12 Correct 111 ms 285004 KB ok
13 Correct 113 ms 285256 KB ok
14 Correct 111 ms 284876 KB ok
15 Correct 111 ms 284896 KB ok
16 Correct 123 ms 284996 KB ok
17 Correct 110 ms 285004 KB ok
18 Correct 109 ms 284976 KB ok
19 Correct 111 ms 284952 KB ok
20 Correct 110 ms 284928 KB ok
21 Correct 119 ms 284948 KB ok
22 Correct 111 ms 284960 KB ok
23 Correct 115 ms 284964 KB ok
24 Correct 109 ms 284944 KB ok
25 Correct 111 ms 284948 KB ok
26 Correct 112 ms 285012 KB ok
27 Correct 109 ms 284984 KB ok
28 Correct 110 ms 285000 KB ok
29 Correct 109 ms 285096 KB ok
30 Correct 113 ms 285132 KB ok
31 Correct 112 ms 285164 KB ok
32 Correct 110 ms 285004 KB ok
33 Correct 108 ms 285004 KB ok
34 Correct 108 ms 285004 KB ok
35 Correct 111 ms 285008 KB ok
36 Correct 109 ms 285004 KB ok
37 Correct 110 ms 284984 KB ok
38 Correct 110 ms 285056 KB ok
39 Correct 126 ms 285132 KB ok
40 Correct 111 ms 285068 KB ok
41 Correct 113 ms 285132 KB ok
42 Correct 1386 ms 348472 KB ok
43 Correct 994 ms 341476 KB ok
44 Correct 1682 ms 356516 KB ok
45 Correct 1758 ms 356976 KB ok
46 Correct 1556 ms 352944 KB ok
47 Correct 1064 ms 354272 KB ok
48 Correct 129 ms 288004 KB ok
49 Correct 658 ms 333200 KB ok
50 Correct 716 ms 336740 KB ok
51 Correct 979 ms 347940 KB ok
52 Correct 260 ms 310768 KB ok
53 Correct 173 ms 306224 KB ok
54 Correct 240 ms 310552 KB ok
55 Correct 335 ms 315420 KB ok
56 Correct 431 ms 325032 KB ok
57 Correct 1103 ms 357768 KB ok
58 Correct 1091 ms 357736 KB ok
59 Correct 1205 ms 357600 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284948 KB ok
2 Correct 110 ms 285004 KB ok
3 Correct 110 ms 284944 KB ok
4 Correct 110 ms 285004 KB ok
5 Correct 110 ms 284896 KB ok
6 Correct 110 ms 284968 KB ok
7 Correct 110 ms 284888 KB ok
8 Correct 111 ms 285108 KB ok
9 Correct 123 ms 287952 KB ok
10 Correct 358 ms 332244 KB ok
11 Correct 108 ms 284928 KB ok
12 Correct 108 ms 285000 KB ok
13 Correct 108 ms 284876 KB ok
14 Correct 109 ms 285132 KB ok
15 Correct 113 ms 285044 KB ok
16 Correct 109 ms 284876 KB ok
17 Correct 111 ms 285004 KB ok
18 Correct 113 ms 285256 KB ok
19 Correct 111 ms 284876 KB ok
20 Correct 111 ms 284896 KB ok
21 Correct 123 ms 284996 KB ok
22 Correct 110 ms 285004 KB ok
23 Correct 109 ms 284976 KB ok
24 Correct 111 ms 284952 KB ok
25 Correct 110 ms 284928 KB ok
26 Correct 119 ms 284948 KB ok
27 Correct 111 ms 284960 KB ok
28 Correct 115 ms 284964 KB ok
29 Correct 109 ms 284944 KB ok
30 Correct 111 ms 284948 KB ok
31 Correct 112 ms 285012 KB ok
32 Correct 109 ms 284984 KB ok
33 Correct 110 ms 285000 KB ok
34 Correct 109 ms 285096 KB ok
35 Correct 113 ms 285132 KB ok
36 Correct 112 ms 285164 KB ok
37 Correct 110 ms 285004 KB ok
38 Correct 108 ms 285004 KB ok
39 Correct 108 ms 285004 KB ok
40 Correct 111 ms 285008 KB ok
41 Correct 109 ms 285004 KB ok
42 Correct 110 ms 284984 KB ok
43 Correct 110 ms 285056 KB ok
44 Correct 126 ms 285132 KB ok
45 Correct 111 ms 285068 KB ok
46 Correct 113 ms 285132 KB ok
47 Correct 1386 ms 348472 KB ok
48 Correct 994 ms 341476 KB ok
49 Correct 1682 ms 356516 KB ok
50 Correct 1758 ms 356976 KB ok
51 Correct 1556 ms 352944 KB ok
52 Correct 1064 ms 354272 KB ok
53 Correct 129 ms 288004 KB ok
54 Correct 658 ms 333200 KB ok
55 Correct 716 ms 336740 KB ok
56 Correct 979 ms 347940 KB ok
57 Correct 260 ms 310768 KB ok
58 Correct 173 ms 306224 KB ok
59 Correct 240 ms 310552 KB ok
60 Correct 335 ms 315420 KB ok
61 Correct 431 ms 325032 KB ok
62 Correct 1103 ms 357768 KB ok
63 Correct 1091 ms 357736 KB ok
64 Correct 1205 ms 357600 KB ok
65 Execution timed out 4636 ms 983172 KB Time limit exceeded
66 Halted 0 ms 0 KB -