Submission #627099

#	Time	Username	Problem	Language	Result	Execution time	Memory
627099		NothingXD	Liteh and Newfiteh (INOI20_litehfiteh)	C++14	100 / 100	97 ms	114576 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int MAXN = 1e5 + 10;
const int LOG = 17;
const int INF = 1e9;
int n, a[MAXN], dp[LOG][LOG][MAXN], ans[MAXN];

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

	memset(dp, 63, sizeof dp);
	memset(ans, 63, sizeof ans);
	debug(2*ans[0]+1);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		if (a[i] > LOG) continue;
		dp[0][a[i]][i] = 0;
		if (a[i]) dp[0][a[i]-1][i] = 1;
	}
	for (int i = 1; i < LOG; i++){
		for (int j = 0; j < LOG - 1; j++){
			for (int k = 1; k + (1 << i) - 1 <= n; k++){
				dp[i][j][k] = min({dp[i][j][k], dp[i-1][j][k] + dp[i-1][j][k + (1 << (i-1))],
						dp[i-1][j+1][k] + dp[i-1][j+1][k + (1 << (i-1))] + 1});
				}
		}
	}
	ans[n+1] = 0;
	for (int i = n; i; i--){
		for (int j = 0; i + (1 << j) - 1 <= n; j++){
			ans[i] = min(ans[i], dp[j][0][i] + ans[i + (1 << j)]);
		}
	}
	cout << (ans[1] >= INF? -1: ans[1]) << '\n';
}

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