oj.uz

Submission #840718

# Submission time Handle Problem Language Result Execution time Memory
840718 2023-08-31T16:12:08 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 378248 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>;

 
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 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]++;
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
    }
 
    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 110 ms 285004 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 285012 KB ok
2 Correct 110 ms 284988 KB ok
3 Correct 116 ms 284912 KB ok
4 Correct 110 ms 285004 KB ok
5 Correct 112 ms 284980 KB ok
6 Correct 113 ms 284916 KB ok
7 Correct 118 ms 288836 KB ok
8 Correct 497 ms 359916 KB ok
9 Execution timed out 4566 ms 378248 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 285012 KB ok
2 Correct 110 ms 284988 KB ok
3 Correct 113 ms 284936 KB ok
4 Correct 113 ms 284980 KB ok
5 Correct 109 ms 284876 KB ok
6 Correct 114 ms 285004 KB ok
7 Correct 116 ms 284904 KB ok
8 Correct 111 ms 284964 KB ok
9 Correct 110 ms 285004 KB ok
10 Correct 119 ms 285112 KB ok
11 Correct 110 ms 284936 KB ok
12 Correct 109 ms 284904 KB ok
13 Correct 112 ms 284924 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 285004 KB ok
2 Correct 109 ms 285012 KB ok
3 Correct 110 ms 284988 KB ok
4 Correct 113 ms 284936 KB ok
5 Correct 113 ms 284980 KB ok
6 Correct 109 ms 284876 KB ok
7 Correct 114 ms 285004 KB ok
8 Correct 116 ms 284904 KB ok
9 Correct 111 ms 284964 KB ok
10 Correct 110 ms 285004 KB ok
11 Correct 119 ms 285112 KB ok
12 Correct 110 ms 284936 KB ok
13 Correct 109 ms 284904 KB ok
14 Correct 112 ms 284924 KB ok
15 Correct 111 ms 284976 KB ok
16 Correct 113 ms 285004 KB ok
17 Correct 129 ms 285004 KB ok
18 Correct 113 ms 285096 KB ok
19 Correct 110 ms 284924 KB ok
20 Correct 110 ms 284980 KB ok
21 Correct 110 ms 284984 KB ok
22 Correct 109 ms 285004 KB ok
23 Correct 110 ms 284900 KB ok
24 Correct 110 ms 284992 KB ok
25 Correct 109 ms 285004 KB ok
26 Correct 110 ms 284948 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 285004 KB ok
2 Correct 109 ms 285012 KB ok
3 Correct 110 ms 284988 KB ok
4 Correct 116 ms 284912 KB ok
5 Correct 110 ms 285004 KB ok
6 Correct 113 ms 284936 KB ok
7 Correct 113 ms 284980 KB ok
8 Correct 109 ms 284876 KB ok
9 Correct 114 ms 285004 KB ok
10 Correct 116 ms 284904 KB ok
11 Correct 111 ms 284964 KB ok
12 Correct 110 ms 285004 KB ok
13 Correct 119 ms 285112 KB ok
14 Correct 110 ms 284936 KB ok
15 Correct 109 ms 284904 KB ok
16 Correct 112 ms 284924 KB ok
17 Correct 111 ms 284976 KB ok
18 Correct 113 ms 285004 KB ok
19 Correct 129 ms 285004 KB ok
20 Correct 113 ms 285096 KB ok
21 Correct 110 ms 284924 KB ok
22 Correct 110 ms 284980 KB ok
23 Correct 110 ms 284984 KB ok
24 Correct 109 ms 285004 KB ok
25 Correct 110 ms 284900 KB ok
26 Correct 110 ms 284992 KB ok
27 Correct 109 ms 285004 KB ok
28 Correct 110 ms 284948 KB ok
29 Correct 113 ms 284908 KB ok
30 Correct 111 ms 285228 KB ok
31 Correct 115 ms 285304 KB ok
32 Correct 111 ms 285068 KB ok
33 Correct 111 ms 285024 KB ok
34 Correct 111 ms 284976 KB ok
35 Correct 112 ms 285004 KB ok
36 Correct 111 ms 285004 KB ok
37 Correct 113 ms 285112 KB ok
38 Correct 111 ms 285192 KB ok
39 Correct 110 ms 285048 KB ok
40 Correct 109 ms 285260 KB ok
41 Correct 111 ms 285232 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 285004 KB ok
2 Correct 109 ms 285012 KB ok
3 Correct 110 ms 284988 KB ok
4 Correct 116 ms 284912 KB ok
5 Correct 110 ms 285004 KB ok
6 Correct 113 ms 284936 KB ok
7 Correct 113 ms 284980 KB ok
8 Correct 109 ms 284876 KB ok
9 Correct 114 ms 285004 KB ok
10 Correct 116 ms 284904 KB ok
11 Correct 111 ms 284964 KB ok
12 Correct 110 ms 285004 KB ok
13 Correct 119 ms 285112 KB ok
14 Correct 110 ms 284936 KB ok
15 Correct 109 ms 284904 KB ok
16 Correct 112 ms 284924 KB ok
17 Correct 111 ms 284976 KB ok
18 Correct 113 ms 285004 KB ok
19 Correct 129 ms 285004 KB ok
20 Correct 113 ms 285096 KB ok
21 Correct 110 ms 284924 KB ok
22 Correct 110 ms 284980 KB ok
23 Correct 110 ms 284984 KB ok
24 Correct 109 ms 285004 KB ok
25 Correct 110 ms 284900 KB ok
26 Correct 110 ms 284992 KB ok
27 Correct 109 ms 285004 KB ok
28 Correct 110 ms 284948 KB ok
29 Correct 113 ms 284908 KB ok
30 Correct 111 ms 285228 KB ok
31 Correct 115 ms 285304 KB ok
32 Correct 111 ms 285068 KB ok
33 Correct 111 ms 285024 KB ok
34 Correct 111 ms 284976 KB ok
35 Correct 112 ms 285004 KB ok
36 Correct 111 ms 285004 KB ok
37 Correct 113 ms 285112 KB ok
38 Correct 111 ms 285192 KB ok
39 Correct 110 ms 285048 KB ok
40 Correct 109 ms 285260 KB ok
41 Correct 111 ms 285232 KB ok
42 Correct 447 ms 358828 KB ok
43 Correct 372 ms 355996 KB ok
44 Correct 594 ms 362796 KB ok
45 Correct 614 ms 363072 KB ok
46 Correct 508 ms 360732 KB ok
47 Correct 555 ms 360092 KB ok
48 Correct 304 ms 334008 KB ok
49 Correct 331 ms 353356 KB ok
50 Correct 389 ms 354336 KB ok
51 Correct 385 ms 359068 KB ok
52 Correct 175 ms 315836 KB ok
53 Correct 149 ms 307012 KB ok
54 Correct 173 ms 311232 KB ok
55 Correct 197 ms 317992 KB ok
56 Correct 258 ms 330948 KB ok
57 Correct 491 ms 363628 KB ok
58 Correct 486 ms 363584 KB ok
59 Correct 476 ms 363396 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 285004 KB ok
2 Correct 109 ms 285012 KB ok
3 Correct 110 ms 284988 KB ok
4 Correct 116 ms 284912 KB ok
5 Correct 110 ms 285004 KB ok
6 Correct 112 ms 284980 KB ok
7 Correct 113 ms 284916 KB ok
8 Correct 118 ms 288836 KB ok
9 Correct 497 ms 359916 KB ok
10 Execution timed out 4566 ms 378248 KB Time limit exceeded
11 Halted 0 ms 0 KB -