Submission #623033

#	Time	Username	Problem	Language	Result	Execution time	Memory
623033		Arinoor	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	0 / 100	1 ms	468 KiB

Main

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

#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;
const int maxlg = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int a[maxn];
int mx[maxlg][maxn];
int mn[maxlg][maxn];
bool dpL[maxn][maxlg], dpR[maxn][maxlg];
int dp[maxn];

int main(){
	ios;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		mx[0][i] = mn[0][i] = a[i];
	}
	for(int i = 1; i < maxlg; i ++){
		for(int j = 0; j + (1 << i) <= n; j ++){
			mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
			mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
		}
	}
	for(int i = 0; i < n; i ++){
		dpL[i][0] = a[i] > 0;
		for(int j = 1; i + (1 << j) <= n and dpL[i][j - 1]; j ++){
			int ind = i + (1 << (j - 1));
			int Mx = mx[j - 1][ind];
			int Mn = mn[j - 1][ind];
			if(Mx ^ Mn or !Mx)
				break;
			dpL[i][j] = Mx <= a[ind - 1] and Mx + 1 >= a[ind - 1];
		}
		dpR[i][0] = a[i] > 0;
		for(int j = 1; i - (1 << j) >= -1 and dpR[i][j - 1]; j ++){
			int ind = i - (1 << j) + 1;
			int Mx = mx[j - 1][ind];
			int Mn = mn[j - 1][ind];
			ind += 1 << (j - 1);
			if(Mx ^ Mn or !Mx)
				break;
			dpR[i][j] = Mx <= a[ind] and Mx + 1 >= a[ind];
		}
	}
	for(int i = n - 1; ~i; i --){
		if(!a[i]){
			dp[i] = dp[i + 1];
			continue;
		}
		dp[i] = a[i] == 1 ? 1 + dp[i + 1] : inf;
		for(int j = 1; i + (1 << j) <= n; j ++){
			int r = i + (1 << j) - 1;
			if(!dpL[i][j - 1] or !dpR[r][j - 1])
				continue;
			int x1 = a[i + (1 << (j - 1))];
			int x2 = a[r - (1 << (j - 1))];
			if(min(x1, x2) < 1 or max(x1, x2) > 2)
				continue;
			dp[i] = min(dp[i], dp[r + 1] + a[i] + a[r] - 1);
		}
	}
	if(dp[0] >= inf)
		dp[0] = -1;
	cout << dp[0] << '\n';
}

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