#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 1e6 + 5;
const int LOG = 20;
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 |
Correct |
1 ms |
860 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
0 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
0 ms |
728 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
0 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
860 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
0 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
0 ms |
728 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
0 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Correct |
0 ms |
472 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
436 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
1116 KB |
Output is correct |
19 |
Correct |
1 ms |
1116 KB |
Output is correct |
20 |
Correct |
6 ms |
10332 KB |
Output is correct |
21 |
Correct |
8 ms |
10328 KB |
Output is correct |
22 |
Correct |
81 ms |
124376 KB |
Output is correct |
23 |
Correct |
67 ms |
123980 KB |
Output is correct |
24 |
Correct |
73 ms |
124244 KB |
Output is correct |
25 |
Correct |
0 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
1116 KB |
Output is correct |
29 |
Correct |
5 ms |
10332 KB |
Output is correct |
30 |
Correct |
6 ms |
10328 KB |
Output is correct |
31 |
Correct |
7 ms |
10332 KB |
Output is correct |
32 |
Correct |
6 ms |
10332 KB |
Output is correct |
33 |
Correct |
73 ms |
124244 KB |
Output is correct |
34 |
Correct |
97 ms |
124244 KB |
Output is correct |
35 |
Correct |
80 ms |
124244 KB |
Output is correct |
36 |
Correct |
74 ms |
124240 KB |
Output is correct |
37 |
Correct |
75 ms |
124244 KB |
Output is correct |
38 |
Correct |
77 ms |
124240 KB |
Output is correct |
39 |
Correct |
80 ms |
124244 KB |
Output is correct |
40 |
Correct |
94 ms |
124452 KB |
Output is correct |
41 |
Correct |
80 ms |
124244 KB |
Output is correct |
42 |
Correct |
95 ms |
124600 KB |
Output is correct |
43 |
Correct |
83 ms |
124244 KB |
Output is correct |
44 |
Correct |
83 ms |
124244 KB |
Output is correct |
45 |
Correct |
83 ms |
124256 KB |
Output is correct |
46 |
Correct |
84 ms |
124240 KB |
Output is correct |
47 |
Correct |
55 ms |
79584 KB |
Output is correct |
48 |
Correct |
63 ms |
94544 KB |
Output is correct |
49 |
Correct |
87 ms |
109392 KB |
Output is correct |
50 |
Correct |
86 ms |
124244 KB |
Output is correct |
51 |
Correct |
7 ms |
10332 KB |
Output is correct |
52 |
Correct |
85 ms |
124276 KB |
Output is correct |