oj.uz

Submission #627096

# Submission time Handle Problem Language Result Execution time Memory
627096 2022-08-12T07:30:00 Z NothingXD Liteh and Newfiteh (INOI20_litehfiteh) C++17
0 / 100
 52 ms 113796 KB 
#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);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		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 < 4; 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 113740 KB Output is correct
2 Correct 43 ms 113744 KB Output is correct
3 Correct 42 ms 113796 KB Output is correct
4 Correct 52 ms 113712 KB Output is correct
5 Incorrect 45 ms 113760 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 113740 KB Output is correct
2 Correct 43 ms 113744 KB Output is correct
3 Correct 42 ms 113796 KB Output is correct
4 Correct 52 ms 113712 KB Output is correct
5 Incorrect 45 ms 113760 KB Output isn't correct
6 Halted 0 ms 0 KB -