#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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
