oj.uz

Submission #840760

# Submission time Handle Problem Language Result Execution time Memory
840760 2023-08-31T16:46:51 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 1599160 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 get_cost(int i, int l, int r) {
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}

#include<bits/extc++.h>

struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;

template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

 
int cnt_l[M][M], cnt_r[M][M];
int store_up[M][M], store_down[M][M];
vector<int> impl[M][M];
vector<int> impr[M][M];
vector<int> has[M][M];
hash_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) {
    for (int j = 0; j < N; j++) {
        int one = 0;
        for (int i = 0; i < N; i++) {
            one = F[i][j] ? 0 : one + 1;
            store_up[i][j] = one;
        }

        int two = 0;
        for (int i = N-1; i >= 0; i--) {
            two = F[i][j] ? 0 : two + 1;
            store_down[i][j] = two;
        }
    }

    for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            up[j] = store_up[i][j], down[j] = store_down[i][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]++;
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
    }
 
    auto add_imp = [&](int i, int l, int r) {
        has[l][r].push_back(i);
        cnt_l[i][l]++, cnt_r[i][r]++;
    };
 
    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++)
        impl[i][j].reserve(cnt_l[i][j]), impr[i][j].reserve(cnt_r[i][j]);

    for (int l = 0; l < N; l++) {
        for (int r = 0; r < N; r++) {
            for (int i : has[l][r]) {
                impl[i][l].push_back(r);
                impr[i][r].push_back(l);
            }
        }
    }
 
    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];
            int& store = dp[h(ni, nl, r)];
            store = max(store, 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];
            int& store = dp[h(ni, l, nr)];
            store = max(store, 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[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, store, cur_cost);
                upd(top, l, r, store, cur_cost);
                upd(bot, l, r, store, 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 117 ms 285092 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 285004 KB ok
2 Correct 115 ms 285028 KB ok
3 Correct 115 ms 285168 KB ok
4 Correct 117 ms 285096 KB ok
5 Correct 112 ms 284952 KB ok
6 Correct 112 ms 285048 KB ok
7 Correct 120 ms 290584 KB ok
8 Correct 376 ms 371824 KB ok
9 Execution timed out 4608 ms 1599160 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 285004 KB ok
2 Correct 115 ms 285028 KB ok
3 Correct 115 ms 285132 KB ok
4 Correct 112 ms 285008 KB ok
5 Correct 113 ms 285036 KB ok
6 Correct 115 ms 284960 KB ok
7 Correct 121 ms 284952 KB ok
8 Correct 116 ms 284948 KB ok
9 Correct 112 ms 285016 KB ok
10 Correct 112 ms 285012 KB ok
11 Correct 112 ms 284976 KB ok
12 Correct 117 ms 285036 KB ok
13 Correct 112 ms 284956 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 285092 KB ok
2 Correct 113 ms 285004 KB ok
3 Correct 115 ms 285028 KB ok
4 Correct 115 ms 285132 KB ok
5 Correct 112 ms 285008 KB ok
6 Correct 113 ms 285036 KB ok
7 Correct 115 ms 284960 KB ok
8 Correct 121 ms 284952 KB ok
9 Correct 116 ms 284948 KB ok
10 Correct 112 ms 285016 KB ok
11 Correct 112 ms 285012 KB ok
12 Correct 112 ms 284976 KB ok
13 Correct 117 ms 285036 KB ok
14 Correct 112 ms 284956 KB ok
15 Correct 112 ms 285128 KB ok
16 Correct 115 ms 285104 KB ok
17 Correct 112 ms 285056 KB ok
18 Correct 113 ms 285144 KB ok
19 Correct 112 ms 285124 KB ok
20 Correct 128 ms 285036 KB ok
21 Correct 115 ms 285028 KB ok
22 Correct 119 ms 285120 KB ok
23 Correct 112 ms 285032 KB ok
24 Correct 112 ms 285004 KB ok
25 Correct 114 ms 285024 KB ok
26 Correct 119 ms 285124 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 285092 KB ok
2 Correct 113 ms 285004 KB ok
3 Correct 115 ms 285028 KB ok
4 Correct 115 ms 285168 KB ok
5 Correct 117 ms 285096 KB ok
6 Correct 115 ms 285132 KB ok
7 Correct 112 ms 285008 KB ok
8 Correct 113 ms 285036 KB ok
9 Correct 115 ms 284960 KB ok
10 Correct 121 ms 284952 KB ok
11 Correct 116 ms 284948 KB ok
12 Correct 112 ms 285016 KB ok
13 Correct 112 ms 285012 KB ok
14 Correct 112 ms 284976 KB ok
15 Correct 117 ms 285036 KB ok
16 Correct 112 ms 284956 KB ok
17 Correct 112 ms 285128 KB ok
18 Correct 115 ms 285104 KB ok
19 Correct 112 ms 285056 KB ok
20 Correct 113 ms 285144 KB ok
21 Correct 112 ms 285124 KB ok
22 Correct 128 ms 285036 KB ok
23 Correct 115 ms 285028 KB ok
24 Correct 119 ms 285120 KB ok
25 Correct 112 ms 285032 KB ok
26 Correct 112 ms 285004 KB ok
27 Correct 114 ms 285024 KB ok
28 Correct 119 ms 285124 KB ok
29 Correct 122 ms 285100 KB ok
30 Correct 113 ms 285788 KB ok
31 Correct 113 ms 285780 KB ok
32 Correct 119 ms 285652 KB ok
33 Correct 112 ms 285428 KB ok
34 Correct 116 ms 285496 KB ok
35 Correct 113 ms 285448 KB ok
36 Correct 113 ms 285372 KB ok
37 Correct 119 ms 285424 KB ok
38 Correct 115 ms 285416 KB ok
39 Correct 112 ms 285440 KB ok
40 Correct 113 ms 285704 KB ok
41 Correct 113 ms 285740 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 285092 KB ok
2 Correct 113 ms 285004 KB ok
3 Correct 115 ms 285028 KB ok
4 Correct 115 ms 285168 KB ok
5 Correct 117 ms 285096 KB ok
6 Correct 115 ms 285132 KB ok
7 Correct 112 ms 285008 KB ok
8 Correct 113 ms 285036 KB ok
9 Correct 115 ms 284960 KB ok
10 Correct 121 ms 284952 KB ok
11 Correct 116 ms 284948 KB ok
12 Correct 112 ms 285016 KB ok
13 Correct 112 ms 285012 KB ok
14 Correct 112 ms 284976 KB ok
15 Correct 117 ms 285036 KB ok
16 Correct 112 ms 284956 KB ok
17 Correct 112 ms 285128 KB ok
18 Correct 115 ms 285104 KB ok
19 Correct 112 ms 285056 KB ok
20 Correct 113 ms 285144 KB ok
21 Correct 112 ms 285124 KB ok
22 Correct 128 ms 285036 KB ok
23 Correct 115 ms 285028 KB ok
24 Correct 119 ms 285120 KB ok
25 Correct 112 ms 285032 KB ok
26 Correct 112 ms 285004 KB ok
27 Correct 114 ms 285024 KB ok
28 Correct 119 ms 285124 KB ok
29 Correct 122 ms 285100 KB ok
30 Correct 113 ms 285788 KB ok
31 Correct 113 ms 285780 KB ok
32 Correct 119 ms 285652 KB ok
33 Correct 112 ms 285428 KB ok
34 Correct 116 ms 285496 KB ok
35 Correct 113 ms 285448 KB ok
36 Correct 113 ms 285372 KB ok
37 Correct 119 ms 285424 KB ok
38 Correct 115 ms 285416 KB ok
39 Correct 112 ms 285440 KB ok
40 Correct 113 ms 285704 KB ok
41 Correct 113 ms 285740 KB ok
42 Correct 420 ms 370120 KB ok
43 Correct 356 ms 367364 KB ok
44 Correct 553 ms 373876 KB ok
45 Correct 508 ms 374296 KB ok
46 Correct 457 ms 371924 KB ok
47 Correct 404 ms 372028 KB ok
48 Correct 253 ms 344504 KB ok
49 Correct 290 ms 363804 KB ok
50 Correct 352 ms 366120 KB ok
51 Correct 393 ms 370372 KB ok
52 Correct 186 ms 324272 KB ok
53 Correct 157 ms 314220 KB ok
54 Correct 178 ms 319836 KB ok
55 Correct 197 ms 327868 KB ok
56 Correct 250 ms 339608 KB ok
57 Correct 415 ms 374852 KB ok
58 Correct 423 ms 374764 KB ok
59 Correct 417 ms 374460 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 285092 KB ok
2 Correct 113 ms 285004 KB ok
3 Correct 115 ms 285028 KB ok
4 Correct 115 ms 285168 KB ok
5 Correct 117 ms 285096 KB ok
6 Correct 112 ms 284952 KB ok
7 Correct 112 ms 285048 KB ok
8 Correct 120 ms 290584 KB ok
9 Correct 376 ms 371824 KB ok
10 Execution timed out 4608 ms 1599160 KB Time limit exceeded
11 Halted 0 ms 0 KB -