Submission #782770

#	Time	Username	Problem	Language	Result	Execution time	Memory
782770		MISM06	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	295 ms	255848 KiB

Main

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll INF = 1e9 + 10;
const ll lg = 18;

ll n, dp[N][lg][lg], pd[N], a[N];

void solve () {

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = n; i >= 1; --i) {
		for (int j = 0; j < lg; j++) dp[i][j][lg - 1] = INF;
		for (int k = lg - 2; k >= 0; --k) {
			int x = a[i] - k;
			if (x != 0) dp[i][0][k] = INF;
			else dp[i][0][k] = 0;
			for (int j = 1; j < lg; j++) {
				if (i + (1 << j) > n + 1) dp[i][j][k] = INF;
				else dp[i][j][k] = min(dp[i][j - 1][k], dp[i][j - 1][k + 1] + 1) + min(dp[i + (1 << (j - 1))][j - 1][k], dp[i + (1 << (j - 1))][j - 1][k + 1] + 1);
			}
		}
	}
	pd[n + 1] = 0;
	for (int i = n; i >= 1; --i) {
		if (a[i] == 0) pd[i] = pd[i + 1];
		else {
			pd[i] = INF;
			for (int j = 0; j < lg; j++) {
				if ((1 << j) + i > n + 1) continue;
				pd[i] = min(pd[i], dp[i][j][1] + 1 + pd[i + (1 << j)]);
			}
		}
	}
	if (pd[1] >= INF) cout << -1 << '\n';
	else cout << pd[1] << '\n';

}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//shrek is love;

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70