#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 1e6 + 5;
const int LOG = 4;
int dp[LOG][MXN][LOG];
int dp1[MXN];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < LOG; i++)
{
for (int j = 1; j + (1LL << i) - 1 <= n; j++)
{
for (int k = 0; k < LOG; k++)
{
if (!i)
{
dp[i][j][k] = (k == a[j] ? 0 : (k == a[j] - 1 ? 1 : inf));
}
else
{
dp[i][j][k] = min(dp[i - 1][j][k] + dp[i - 1][j + (1LL << (i - 1))][k], dp[i - 1][j][k + 1] + dp[i - 1][j + (1LL << (i - 1))][k + 1] + 1);
dp[i][j][k] = min(dp[i][j][k], inf);
}
}
}
}
for (int i = 1; i <= n; i++)
{
if (a[i] > LOG)
{
cout << -1 << '\n';
return 0;
}
dp1[i] = inf;
for (int j = 0; j < LOG && i - (1LL << j) >= 0; j++)
{
dp1[i] = min(dp1[i], dp1[i - (1LL << j)] + dp[j][i - (1LL << j) + 1][0]);
}
}
cout << (dp1[n] >= inf ? -1 : dp1[n]) << '\n';
}
// 10
// 1 1 1 1 2 2 2 3 2 1
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
