Submission #623055

#	Time	Username	Problem	Language	Result	Execution time	Memory
623055		Arinoor	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	108 ms	112528 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 = 18;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int a[maxn];
int Dp[maxlg][maxlg][maxn];
int dp[maxn];

int main(){
	ios;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		for(int j = 0; j < maxlg; j ++){
			int &r = Dp[0][j][i];
			int x = a[i] - j;
			if(x < 0 or x > 1)
				r = inf;
			else
				r = x;
		}
	}
	for(int i = 1; i < maxlg; i ++){
		for(int j = 0; j < maxlg; j ++){
			for(int ind = 0; ind + (1 << i) <= n; ind ++){
				int &r = Dp[i][j][ind];
				r = min(inf, Dp[i - 1][j][ind] + Dp[i - 1][j][ind + (1 << (i - 1))]);
				if(j < maxlg - 1){
					r = min(r, 1 + Dp[i - 1][j + 1][ind] + Dp[i - 1][j + 1][ind + (1 << (i - 1))]);
				}
			}
		}
	}
	for(int i = n - 1; ~i; i --){
		if(!a[i]){
			dp[i] = dp[i + 1];
			continue;
		}
		dp[i] = inf;
		for(int j = 0; i + (1 << j) <= n; j ++){
			dp[i] = min(dp[i], Dp[j][0][i] + dp[i + (1 << j)]);
		}
	}
	if(dp[0] >= inf)
		dp[0] = -1;
	cout << dp[0] << '\n';
}

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