#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 = 18;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
int a[maxn];
int Dp[maxlg][maxlg][maxn];
int dp[maxn];
int main(){
ios;
int n;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> a[i];
for(int j = 0; j < maxlg; j ++){
int &r = Dp[0][j][i];
int x = a[i] - j;
if(x < 0 or x > 1)
r = inf;
else
r = x;
}
}
for(int i = 1; i < maxlg; i ++){
for(int j = 0; j < maxlg; j ++){
for(int ind = 0; ind + (1 << i) <= n; ind ++){
int &r = Dp[i][j][ind];
r = min(inf, Dp[i - 1][j][ind] + Dp[i - 1][j][ind + (1 << (i - 1))]);
if(j < maxlg - 1){
r = min(r, 1 + Dp[i - 1][j + 1][ind] + Dp[i - 1][j + 1][ind + (1 << (i - 1))]);
}
}
}
}
for(int i = n - 1; ~i; i --){
if(!a[i]){
dp[i] = dp[i + 1];
continue;
}
dp[i] = inf;
for(int j = 1; i + (1 << j) <= n; j ++){
dp[i] = min(dp[i], Dp[j][0][i] + dp[i + (1 << j)]);
}
}
if(dp[0] >= inf)
dp[0] = -1;
cout << dp[0] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
