oj.uz

Submission #635844

# Submission time Handle Problem Language Result Execution time Memory
635844 2022-08-27T07:47:29 Z S2speed Liteh and Newfiteh (INOI20_litehfiteh) C++17
100 / 100
 244 ms 315136 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 1e5 + 17 , inf = 2e6;

ll a[maxn];
ll pd[20][maxn][20] , dp[maxn];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	for(ll i = 0 ; i < maxn ; i++){
		for(ll j = 0 ; j < 20 ; j++){
			for(ll k = 0 ; k < 20 ; k++){
				pd[j][i][k] = inf;
			}
		}
		dp[i] = inf;
	}
	ll n;
	cin>>n;
	for(ll i = 0 ; i < n ; i++){
		cin>>a[i];
		if(a[i] > 19){
			cout<<"-1\n";
			return 0;
		}
		pd[0][i][a[i]] = 0;
	}
	for(ll j = 1 , z = 1 ; z < n ; j++ , z <<= 1){
		for(ll i = 0 ; i < n - z ; i++){
			for(ll k = 1 ; k < 19 ; k++){
				ll h = min(pd[j - 1][i][k] , pd[j - 1][i][k + 1] + 1);
				h += min(pd[j - 1][i + z][k] , pd[j - 1][i + z][k + 1] + 1);
				pd[j][i][k] = h;
			}
		}
		for(ll i = n - z ; i < n ; i++){
			for(ll k = 1 ; k < 19 ; k++){
				pd[j][i][k] = pd[j - 1][i][k];
			}
		}
	}
	dp[n] = 0;
	for(ll i = n - 1 ; ~i ; i--){
		ll h = inf;
		for(ll j = 0 , z = 1 ; i + z <= n ; j++ , z <<= 1){
			h = min(h , pd[j][i][1] + dp[i + z] + 1);
		}
		dp[i] = h;
	}
	cout<<(dp[0] == inf ? -1 : dp[0])<<'\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 314152 KB Output is correct
2 Correct 142 ms 314336 KB Output is correct
3 Correct 125 ms 314228 KB Output is correct
4 Correct 128 ms 314264 KB Output is correct
5 Correct 155 ms 314152 KB Output is correct
6 Correct 128 ms 314176 KB Output is correct
7 Correct 124 ms 314196 KB Output is correct
8 Correct 122 ms 314444 KB Output is correct
9 Correct 135 ms 314160 KB Output is correct
10 Correct 140 ms 314344 KB Output is correct
11 Correct 123 ms 314156 KB Output is correct
12 Correct 140 ms 314252 KB Output is correct
13 Correct 151 ms 314188 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 314152 KB Output is correct
2 Correct 142 ms 314336 KB Output is correct
3 Correct 125 ms 314228 KB Output is correct
4 Correct 128 ms 314264 KB Output is correct
5 Correct 155 ms 314152 KB Output is correct
6 Correct 128 ms 314176 KB Output is correct
7 Correct 124 ms 314196 KB Output is correct
8 Correct 122 ms 314444 KB Output is correct
9 Correct 135 ms 314160 KB Output is correct
10 Correct 140 ms 314344 KB Output is correct
11 Correct 123 ms 314156 KB Output is correct
12 Correct 140 ms 314252 KB Output is correct
13 Correct 151 ms 314188 KB Output is correct
14 Correct 136 ms 314148 KB Output is correct
15 Correct 124 ms 314224 KB Output is correct
16 Correct 135 ms 314192 KB Output is correct
17 Correct 124 ms 314276 KB Output is correct
18 Correct 134 ms 314236 KB Output is correct
19 Correct 133 ms 314136 KB Output is correct
20 Correct 137 ms 314260 KB Output is correct
21 Correct 149 ms 314264 KB Output is correct
22 Correct 216 ms 314928 KB Output is correct
23 Correct 147 ms 314324 KB Output is correct
24 Correct 215 ms 315028 KB Output is correct
25 Correct 125 ms 314232 KB Output is correct
26 Correct 129 ms 314192 KB Output is correct
27 Correct 137 ms 314252 KB Output is correct
28 Correct 124 ms 314328 KB Output is correct
29 Correct 136 ms 314224 KB Output is correct
30 Correct 144 ms 314260 KB Output is correct
31 Correct 157 ms 314324 KB Output is correct
32 Correct 137 ms 314316 KB Output is correct
33 Correct 200 ms 315020 KB Output is correct
34 Correct 220 ms 315000 KB Output is correct
35 Correct 214 ms 315052 KB Output is correct
36 Correct 203 ms 314964 KB Output is correct
37 Correct 194 ms 314992 KB Output is correct
38 Correct 244 ms 315128 KB Output is correct
39 Correct 195 ms 315028 KB Output is correct
40 Correct 208 ms 315032 KB Output is correct
41 Correct 209 ms 314956 KB Output is correct
42 Correct 197 ms 315084 KB Output is correct
43 Correct 192 ms 315136 KB Output is correct
44 Correct 206 ms 314920 KB Output is correct
45 Correct 194 ms 314956 KB Output is correct
46 Correct 192 ms 315072 KB Output is correct
47 Correct 169 ms 314736 KB Output is correct
48 Correct 192 ms 314736 KB Output is correct
49 Correct 202 ms 314876 KB Output is correct
50 Correct 189 ms 314944 KB Output is correct
51 Correct 131 ms 314232 KB Output is correct
52 Correct 195 ms 315084 KB Output is correct