Submission #676372

#	Time	Username	Problem	Language	Result	Execution time	Memory
676372		valerikk	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	114 ms	27316 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;
const int L = 22;
const int INF = 0x3f3f3f3f;

int n;
int a[N];
int dp[N][L];
int ndp[N][L];
int mn[N][L];
int kek[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		if (a[i] >= L) {
			cout << "-1\n";
			return 0;
		}
	}
	memset(dp, 0x3f, sizeof dp);
	for (int i = 0; i < n; ++i) {
		dp[i][a[i]] = 0;
		if (a[i] > 0) {
			dp[i][a[i] - 1] = 1;
		}
	}
	for (int i = 0; i < n; ++i) {
		mn[i][0] = dp[i][0];
	}
	for (int t = 1; (1 << t) <= n; ++t) {
		memset(ndp, 0x3f, sizeof ndp);
		for (int i = 0; i + (1 << t) <= n; ++i) {
			for (int j = 0; j < L; ++j) {
				ndp[i][j] = min(ndp[i][j], dp[i][j] + dp[i + (1 << (t - 1))][j]);
				if (j + 1 < L) {
					ndp[i][j] = min(ndp[i][j], dp[i][j + 1] + dp[i + (1 << (t - 1))][j + 1] + 1);
				}
			}
		}
		memcpy(dp, ndp, sizeof dp);
		for (int i = 0; i + (1 << t) <= n; ++i) {
			mn[i][t] = dp[i][0];
		}
	}
	memset(kek, 0x3f, sizeof kek);
	kek[n] = 0;
	for (int i = n - 1; i >= 0; --i) {
		for (int t = 0; i + (1 << t) <= n; ++t) {
			kek[i] = min(kek[i], kek[i + (1 << t)] + mn[i][t]);
		}
	}
	if (kek[0] == INF) {
		cout << "-1\n";
		return 0;
	}
	cout << kek[0] << endl;
	return 0;
}

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