This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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; 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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |