This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Be Name Khoda
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
const ll mxn = 1e5 + 16, lg = 18, INF = 1e16 + 16;
ll n, q, w, e;
ll dp[mxn], mn[mxn][lg], pd[mxn][lg][lg];
vector<ll> g;
bool bomb;
inline void input() {
for(int i = 0; i < mxn; i++) {
dp[i] = INF;
for(int j = 0; j < lg; j++) {
mn[i][j] = INF;
fill(pd[i][j], pd[i][j] + lg, INF);
}
}
cin >> n;
for(int i = 0; i < n; i++) {
cin >> q;
g.push_back(q);
if(q >= lg) bomb = 1;
mn[i][0] = q;
}
}
inline void solve() {
if(bomb) {
cout << "-1\n";
return;
}
for(int j = 1; j < lg; j++) {
for(int i = 0; i < n; i++) {
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
}
}
for(int i = 0; i < n; i++) {
for(int k = 0; k < lg; k++) {
if(k == g[i] - 1) {
pd[i][0][k] = 1;
} if(k == g[i]) {
pd[i][0][k] = 0;
}
}
}
for(int j = 1; j < lg; j++) {
for(int i = 0; i < n; i++) {
if(i + (1 << j) > n) break;
for(int k = 0; k < lg; k++) {
if(mn[i][j] < k) break;
pd[i][j][k] = min(INF, pd[i][j - 1][k] + pd[i + (1 << (j - 1))][j - 1][k]);
if(k + 1 < lg && mn[i][j] >= k + 1) {
pd[i][j][k] = min(pd[i][j][k], pd[i][j - 1][k + 1] + pd[i + (1 << (j - 1))][j - 1][k + 1] + 1);
}
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; (1 << j) <= i + 1; j++) {
if((1 << j) == i + 1) {
dp[i] = min(dp[i], pd[0][j][0]);
continue;
}
dp[i] = min(dp[i], pd[i - (1 << j) + 1][j][0] + dp[i - (1 << j)]);
}
}
if(dp[n - 1] >= INF) {
cout << "-1\n";
return;
} cout << dp[n - 1] << endl;
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
/*
8
2 2 2 0 1 1 2 2
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |