oj.uz

Submission #840704

# Submission time Handle Problem Language Result Execution time Memory
840704 2023-08-31T16:05:26 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1027788 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 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[M], twos[M];
 
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);
}
 
vector<int> impl[M][M];
vector<int> impr[M][M];
vector<int> has[M][M];
unordered_map<ll, int> dp;
 
ll h(int a, int b, int c) {
    return (long long) a * M * M + b * M + c;
}

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[h(ni, nl, r)] = max(dp[h(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[h(ni, l, nr)] = max(dp[h(ni, l, nr)], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };
 
    // cerr << (double) clock() / CLOCKS_PER_SEC << endl;
    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[h(i, l, r)] = max(dp[h(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[h(i, l, r)], cur_cost);
                upd(top, l, r, dp[h(i, l, r)], cur_cost);
                upd(bot, l, r, dp[h(i, l, r)], cur_cost);
            }
        }
    }
 
    int ans = 0;
    for (auto& [_, v] : dp) 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 114 ms 284936 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284888 KB ok
2 Correct 119 ms 284908 KB ok
3 Correct 115 ms 284916 KB ok
4 Correct 114 ms 284892 KB ok
5 Correct 114 ms 284908 KB ok
6 Correct 111 ms 284944 KB ok
7 Correct 126 ms 285064 KB ok
8 Correct 127 ms 287904 KB ok
9 Correct 366 ms 332224 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 284888 KB ok
2 Correct 119 ms 284908 KB ok
3 Correct 116 ms 284972 KB ok
4 Correct 113 ms 284900 KB ok
5 Correct 113 ms 284972 KB ok
6 Correct 111 ms 284904 KB ok
7 Correct 129 ms 284948 KB ok
8 Correct 112 ms 284988 KB ok
9 Correct 112 ms 284964 KB ok
10 Correct 113 ms 284956 KB ok
11 Correct 115 ms 284976 KB ok
12 Correct 131 ms 284876 KB ok
13 Correct 112 ms 284944 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 284936 KB ok
2 Correct 112 ms 284888 KB ok
3 Correct 119 ms 284908 KB ok
4 Correct 116 ms 284972 KB ok
5 Correct 113 ms 284900 KB ok
6 Correct 113 ms 284972 KB ok
7 Correct 111 ms 284904 KB ok
8 Correct 129 ms 284948 KB ok
9 Correct 112 ms 284988 KB ok
10 Correct 112 ms 284964 KB ok
11 Correct 113 ms 284956 KB ok
12 Correct 115 ms 284976 KB ok
13 Correct 131 ms 284876 KB ok
14 Correct 112 ms 284944 KB ok
15 Correct 111 ms 284980 KB ok
16 Correct 111 ms 284996 KB ok
17 Correct 119 ms 284932 KB ok
18 Correct 117 ms 284960 KB ok
19 Correct 114 ms 284900 KB ok
20 Correct 112 ms 284972 KB ok
21 Correct 113 ms 284956 KB ok
22 Correct 108 ms 285004 KB ok
23 Correct 118 ms 284912 KB ok
24 Correct 110 ms 284968 KB ok
25 Correct 123 ms 284936 KB ok
26 Correct 115 ms 284932 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 284936 KB ok
2 Correct 112 ms 284888 KB ok
3 Correct 119 ms 284908 KB ok
4 Correct 115 ms 284916 KB ok
5 Correct 114 ms 284892 KB ok
6 Correct 116 ms 284972 KB ok
7 Correct 113 ms 284900 KB ok
8 Correct 113 ms 284972 KB ok
9 Correct 111 ms 284904 KB ok
10 Correct 129 ms 284948 KB ok
11 Correct 112 ms 284988 KB ok
12 Correct 112 ms 284964 KB ok
13 Correct 113 ms 284956 KB ok
14 Correct 115 ms 284976 KB ok
15 Correct 131 ms 284876 KB ok
16 Correct 112 ms 284944 KB ok
17 Correct 111 ms 284980 KB ok
18 Correct 111 ms 284996 KB ok
19 Correct 119 ms 284932 KB ok
20 Correct 117 ms 284960 KB ok
21 Correct 114 ms 284900 KB ok
22 Correct 112 ms 284972 KB ok
23 Correct 113 ms 284956 KB ok
24 Correct 108 ms 285004 KB ok
25 Correct 118 ms 284912 KB ok
26 Correct 110 ms 284968 KB ok
27 Correct 123 ms 284936 KB ok
28 Correct 115 ms 284932 KB ok
29 Correct 112 ms 284992 KB ok
30 Correct 124 ms 285096 KB ok
31 Correct 114 ms 285120 KB ok
32 Correct 121 ms 285016 KB ok
33 Correct 117 ms 285044 KB ok
34 Correct 112 ms 284948 KB ok
35 Correct 110 ms 284920 KB ok
36 Correct 111 ms 285008 KB ok
37 Correct 113 ms 285072 KB ok
38 Correct 114 ms 284992 KB ok
39 Correct 111 ms 285096 KB ok
40 Correct 117 ms 285044 KB ok
41 Correct 119 ms 285092 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 284936 KB ok
2 Correct 112 ms 284888 KB ok
3 Correct 119 ms 284908 KB ok
4 Correct 115 ms 284916 KB ok
5 Correct 114 ms 284892 KB ok
6 Correct 116 ms 284972 KB ok
7 Correct 113 ms 284900 KB ok
8 Correct 113 ms 284972 KB ok
9 Correct 111 ms 284904 KB ok
10 Correct 129 ms 284948 KB ok
11 Correct 112 ms 284988 KB ok
12 Correct 112 ms 284964 KB ok
13 Correct 113 ms 284956 KB ok
14 Correct 115 ms 284976 KB ok
15 Correct 131 ms 284876 KB ok
16 Correct 112 ms 284944 KB ok
17 Correct 111 ms 284980 KB ok
18 Correct 111 ms 284996 KB ok
19 Correct 119 ms 284932 KB ok
20 Correct 117 ms 284960 KB ok
21 Correct 114 ms 284900 KB ok
22 Correct 112 ms 284972 KB ok
23 Correct 113 ms 284956 KB ok
24 Correct 108 ms 285004 KB ok
25 Correct 118 ms 284912 KB ok
26 Correct 110 ms 284968 KB ok
27 Correct 123 ms 284936 KB ok
28 Correct 115 ms 284932 KB ok
29 Correct 112 ms 284992 KB ok
30 Correct 124 ms 285096 KB ok
31 Correct 114 ms 285120 KB ok
32 Correct 121 ms 285016 KB ok
33 Correct 117 ms 285044 KB ok
34 Correct 112 ms 284948 KB ok
35 Correct 110 ms 284920 KB ok
36 Correct 111 ms 285008 KB ok
37 Correct 113 ms 285072 KB ok
38 Correct 114 ms 284992 KB ok
39 Correct 111 ms 285096 KB ok
40 Correct 117 ms 285044 KB ok
41 Correct 119 ms 285092 KB ok
42 Correct 536 ms 341052 KB ok
43 Correct 422 ms 338192 KB ok
44 Correct 738 ms 346588 KB ok
45 Correct 743 ms 347108 KB ok
46 Correct 603 ms 343976 KB ok
47 Correct 587 ms 344300 KB ok
48 Correct 133 ms 288004 KB ok
49 Correct 352 ms 327436 KB ok
50 Correct 432 ms 329716 KB ok
51 Correct 509 ms 341336 KB ok
52 Correct 196 ms 309320 KB ok
53 Correct 164 ms 305832 KB ok
54 Correct 183 ms 309256 KB ok
55 Correct 217 ms 313416 KB ok
56 Correct 249 ms 321864 KB ok
57 Correct 545 ms 347732 KB ok
58 Correct 540 ms 347644 KB ok
59 Correct 546 ms 347572 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 284936 KB ok
2 Correct 112 ms 284888 KB ok
3 Correct 119 ms 284908 KB ok
4 Correct 115 ms 284916 KB ok
5 Correct 114 ms 284892 KB ok
6 Correct 114 ms 284908 KB ok
7 Correct 111 ms 284944 KB ok
8 Correct 126 ms 285064 KB ok
9 Correct 127 ms 287904 KB ok
10 Correct 366 ms 332224 KB ok
11 Correct 116 ms 284972 KB ok
12 Correct 113 ms 284900 KB ok
13 Correct 113 ms 284972 KB ok
14 Correct 111 ms 284904 KB ok
15 Correct 129 ms 284948 KB ok
16 Correct 112 ms 284988 KB ok
17 Correct 112 ms 284964 KB ok
18 Correct 113 ms 284956 KB ok
19 Correct 115 ms 284976 KB ok
20 Correct 131 ms 284876 KB ok
21 Correct 112 ms 284944 KB ok
22 Correct 111 ms 284980 KB ok
23 Correct 111 ms 284996 KB ok
24 Correct 119 ms 284932 KB ok
25 Correct 117 ms 284960 KB ok
26 Correct 114 ms 284900 KB ok
27 Correct 112 ms 284972 KB ok
28 Correct 113 ms 284956 KB ok
29 Correct 108 ms 285004 KB ok
30 Correct 118 ms 284912 KB ok
31 Correct 110 ms 284968 KB ok
32 Correct 123 ms 284936 KB ok
33 Correct 115 ms 284932 KB ok
34 Correct 112 ms 284992 KB ok
35 Correct 124 ms 285096 KB ok
36 Correct 114 ms 285120 KB ok
37 Correct 121 ms 285016 KB ok
38 Correct 117 ms 285044 KB ok
39 Correct 112 ms 284948 KB ok
40 Correct 110 ms 284920 KB ok
41 Correct 111 ms 285008 KB ok
42 Correct 113 ms 285072 KB ok
43 Correct 114 ms 284992 KB ok
44 Correct 111 ms 285096 KB ok
45 Correct 117 ms 285044 KB ok
46 Correct 119 ms 285092 KB ok
47 Correct 536 ms 341052 KB ok
48 Correct 422 ms 338192 KB ok
49 Correct 738 ms 346588 KB ok
50 Correct 743 ms 347108 KB ok
51 Correct 603 ms 343976 KB ok
52 Correct 587 ms 344300 KB ok
53 Correct 133 ms 288004 KB ok
54 Correct 352 ms 327436 KB ok
55 Correct 432 ms 329716 KB ok
56 Correct 509 ms 341336 KB ok
57 Correct 196 ms 309320 KB ok
58 Correct 164 ms 305832 KB ok
59 Correct 183 ms 309256 KB ok
60 Correct 217 ms 313416 KB ok
61 Correct 249 ms 321864 KB ok
62 Correct 545 ms 347732 KB ok
63 Correct 540 ms 347644 KB ok
64 Correct 546 ms 347572 KB ok
65 Execution timed out 4582 ms 1027788 KB Time limit exceeded
66 Halted 0 ms 0 KB -