Submission #635844

#	Time	Username	Problem	Language	Result	Execution time	Memory
635844		S2speed	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	244 ms	315136 KiB

Main

#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 / 30
• Subtask 2: 70 / 70