oj.uz

Submission #840670

# Submission time Handle Problem Language Result Execution time Memory
840670 2023-08-31T15:23:47 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
28 / 100
 4500 ms 1008664 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);
                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) {
        if (ni < 0 || ni >= N) return;
        // cerr << ni << ' ' << l << ' ' << r << ' ' << x << endl;
        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) - get_cost(ni, l, r)) * (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) - get_cost(ni, l, r)) * (nr - l + 1));
        }
    };

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

                int top = i - ones[i].qry(l, r) + 1;
                int bot = i + twos[i].qry(l, r) - 1;
                upd(i, l, r, dp[{i, l, r}]);
                upd(top, l, r, dp[{i, l, r}]);
                upd(bot, l, r, dp[{i, l, r}]);
            }
        }
    }

    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 284900 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 284888 KB ok
2 Correct 109 ms 284980 KB ok
3 Correct 108 ms 284948 KB ok
4 Correct 111 ms 284976 KB ok
5 Correct 108 ms 284924 KB ok
6 Correct 110 ms 284920 KB ok
7 Correct 111 ms 285016 KB ok
8 Correct 149 ms 287992 KB ok
9 Correct 358 ms 332292 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 284888 KB ok
2 Correct 109 ms 284980 KB ok
3 Correct 110 ms 284952 KB ok
4 Correct 113 ms 285024 KB ok
5 Correct 108 ms 284976 KB ok
6 Correct 107 ms 284888 KB ok
7 Correct 110 ms 284996 KB ok
8 Correct 109 ms 284968 KB ok
9 Correct 109 ms 284900 KB ok
10 Correct 109 ms 284940 KB ok
11 Correct 110 ms 284940 KB ok
12 Correct 109 ms 284888 KB ok
13 Correct 109 ms 284880 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284900 KB ok
2 Correct 109 ms 284888 KB ok
3 Correct 109 ms 284980 KB ok
4 Correct 110 ms 284952 KB ok
5 Correct 113 ms 285024 KB ok
6 Correct 108 ms 284976 KB ok
7 Correct 107 ms 284888 KB ok
8 Correct 110 ms 284996 KB ok
9 Correct 109 ms 284968 KB ok
10 Correct 109 ms 284900 KB ok
11 Correct 109 ms 284940 KB ok
12 Correct 110 ms 284940 KB ok
13 Correct 109 ms 284888 KB ok
14 Correct 109 ms 284880 KB ok
15 Partially correct 109 ms 284904 KB partial
16 Partially correct 108 ms 285000 KB partial
17 Correct 109 ms 284972 KB ok
18 Correct 111 ms 284932 KB ok
19 Partially correct 109 ms 284888 KB partial
20 Correct 110 ms 284952 KB ok
21 Correct 109 ms 284976 KB ok
22 Correct 113 ms 284924 KB ok
23 Correct 109 ms 284888 KB ok
24 Partially correct 110 ms 284892 KB partial
25 Partially correct 108 ms 284980 KB partial
26 Correct 109 ms 284952 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284900 KB ok
2 Correct 109 ms 284888 KB ok
3 Correct 109 ms 284980 KB ok
4 Correct 108 ms 284948 KB ok
5 Correct 111 ms 284976 KB ok
6 Correct 110 ms 284952 KB ok
7 Correct 113 ms 285024 KB ok
8 Correct 108 ms 284976 KB ok
9 Correct 107 ms 284888 KB ok
10 Correct 110 ms 284996 KB ok
11 Correct 109 ms 284968 KB ok
12 Correct 109 ms 284900 KB ok
13 Correct 109 ms 284940 KB ok
14 Correct 110 ms 284940 KB ok
15 Correct 109 ms 284888 KB ok
16 Correct 109 ms 284880 KB ok
17 Partially correct 109 ms 284904 KB partial
18 Partially correct 108 ms 285000 KB partial
19 Correct 109 ms 284972 KB ok
20 Correct 111 ms 284932 KB ok
21 Partially correct 109 ms 284888 KB partial
22 Correct 110 ms 284952 KB ok
23 Correct 109 ms 284976 KB ok
24 Correct 113 ms 284924 KB ok
25 Correct 109 ms 284888 KB ok
26 Partially correct 110 ms 284892 KB partial
27 Partially correct 108 ms 284980 KB partial
28 Correct 109 ms 284952 KB ok
29 Correct 110 ms 284908 KB ok
30 Correct 114 ms 285332 KB ok
31 Correct 112 ms 285172 KB ok
32 Correct 122 ms 285008 KB ok
33 Partially correct 110 ms 284944 KB partial
34 Correct 112 ms 284944 KB ok
35 Correct 115 ms 284944 KB ok
36 Correct 111 ms 284992 KB ok
37 Partially correct 113 ms 285000 KB partial
38 Partially correct 111 ms 285052 KB partial
39 Partially correct 110 ms 285036 KB partial
40 Partially correct 110 ms 285084 KB partial
41 Correct 113 ms 285224 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284900 KB ok
2 Correct 109 ms 284888 KB ok
3 Correct 109 ms 284980 KB ok
4 Correct 108 ms 284948 KB ok
5 Correct 111 ms 284976 KB ok
6 Correct 110 ms 284952 KB ok
7 Correct 113 ms 285024 KB ok
8 Correct 108 ms 284976 KB ok
9 Correct 107 ms 284888 KB ok
10 Correct 110 ms 284996 KB ok
11 Correct 109 ms 284968 KB ok
12 Correct 109 ms 284900 KB ok
13 Correct 109 ms 284940 KB ok
14 Correct 110 ms 284940 KB ok
15 Correct 109 ms 284888 KB ok
16 Correct 109 ms 284880 KB ok
17 Partially correct 109 ms 284904 KB partial
18 Partially correct 108 ms 285000 KB partial
19 Correct 109 ms 284972 KB ok
20 Correct 111 ms 284932 KB ok
21 Partially correct 109 ms 284888 KB partial
22 Correct 110 ms 284952 KB ok
23 Correct 109 ms 284976 KB ok
24 Correct 113 ms 284924 KB ok
25 Correct 109 ms 284888 KB ok
26 Partially correct 110 ms 284892 KB partial
27 Partially correct 108 ms 284980 KB partial
28 Correct 109 ms 284952 KB ok
29 Correct 110 ms 284908 KB ok
30 Correct 114 ms 285332 KB ok
31 Correct 112 ms 285172 KB ok
32 Correct 122 ms 285008 KB ok
33 Partially correct 110 ms 284944 KB partial
34 Correct 112 ms 284944 KB ok
35 Correct 115 ms 284944 KB ok
36 Correct 111 ms 284992 KB ok
37 Partially correct 113 ms 285000 KB partial
38 Partially correct 111 ms 285052 KB partial
39 Partially correct 110 ms 285036 KB partial
40 Partially correct 110 ms 285084 KB partial
41 Correct 113 ms 285224 KB ok
42 Partially correct 991 ms 348764 KB partial
43 Partially correct 888 ms 341876 KB partial
44 Partially correct 1154 ms 356600 KB partial
45 Partially correct 1172 ms 357136 KB partial
46 Partially correct 1119 ms 353144 KB partial
47 Partially correct 1048 ms 354388 KB partial
48 Correct 125 ms 287916 KB ok
49 Partially correct 627 ms 333132 KB partial
50 Partially correct 653 ms 336936 KB partial
51 Correct 923 ms 348124 KB ok
52 Partially correct 239 ms 310728 KB partial
53 Partially correct 179 ms 306260 KB partial
54 Partially correct 245 ms 310612 KB partial
55 Partially correct 302 ms 315340 KB partial
56 Partially correct 459 ms 325044 KB partial
57 Correct 1160 ms 357836 KB ok
58 Correct 1153 ms 357660 KB ok
59 Correct 1175 ms 357552 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 284900 KB ok
2 Correct 109 ms 284888 KB ok
3 Correct 109 ms 284980 KB ok
4 Correct 108 ms 284948 KB ok
5 Correct 111 ms 284976 KB ok
6 Correct 108 ms 284924 KB ok
7 Correct 110 ms 284920 KB ok
8 Correct 111 ms 285016 KB ok
9 Correct 149 ms 287992 KB ok
10 Correct 358 ms 332292 KB ok
11 Correct 110 ms 284952 KB ok
12 Correct 113 ms 285024 KB ok
13 Correct 108 ms 284976 KB ok
14 Correct 107 ms 284888 KB ok
15 Correct 110 ms 284996 KB ok
16 Correct 109 ms 284968 KB ok
17 Correct 109 ms 284900 KB ok
18 Correct 109 ms 284940 KB ok
19 Correct 110 ms 284940 KB ok
20 Correct 109 ms 284888 KB ok
21 Correct 109 ms 284880 KB ok
22 Partially correct 109 ms 284904 KB partial
23 Partially correct 108 ms 285000 KB partial
24 Correct 109 ms 284972 KB ok
25 Correct 111 ms 284932 KB ok
26 Partially correct 109 ms 284888 KB partial
27 Correct 110 ms 284952 KB ok
28 Correct 109 ms 284976 KB ok
29 Correct 113 ms 284924 KB ok
30 Correct 109 ms 284888 KB ok
31 Partially correct 110 ms 284892 KB partial
32 Partially correct 108 ms 284980 KB partial
33 Correct 109 ms 284952 KB ok
34 Correct 110 ms 284908 KB ok
35 Correct 114 ms 285332 KB ok
36 Correct 112 ms 285172 KB ok
37 Correct 122 ms 285008 KB ok
38 Partially correct 110 ms 284944 KB partial
39 Correct 112 ms 284944 KB ok
40 Correct 115 ms 284944 KB ok
41 Correct 111 ms 284992 KB ok
42 Partially correct 113 ms 285000 KB partial
43 Partially correct 111 ms 285052 KB partial
44 Partially correct 110 ms 285036 KB partial
45 Partially correct 110 ms 285084 KB partial
46 Correct 113 ms 285224 KB ok
47 Partially correct 991 ms 348764 KB partial
48 Partially correct 888 ms 341876 KB partial
49 Partially correct 1154 ms 356600 KB partial
50 Partially correct 1172 ms 357136 KB partial
51 Partially correct 1119 ms 353144 KB partial
52 Partially correct 1048 ms 354388 KB partial
53 Correct 125 ms 287916 KB ok
54 Partially correct 627 ms 333132 KB partial
55 Partially correct 653 ms 336936 KB partial
56 Correct 923 ms 348124 KB ok
57 Partially correct 239 ms 310728 KB partial
58 Partially correct 179 ms 306260 KB partial
59 Partially correct 245 ms 310612 KB partial
60 Partially correct 302 ms 315340 KB partial
61 Partially correct 459 ms 325044 KB partial
62 Correct 1160 ms 357836 KB ok
63 Correct 1153 ms 357660 KB ok
64 Correct 1175 ms 357552 KB ok
65 Execution timed out 4571 ms 1008664 KB Time limit exceeded
66 Halted 0 ms 0 KB -