# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
416633 | parsabahrami | Liteh and Newfiteh (INOI20_litehfiteh) | C++17 | 182 ms | 142664 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 1e5 + 10, MOD = 1e9 + 7;
int dp[19][19][N], A[N], pd[N], n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
for (int i = 1; i <= n; i++) if (A[i] >= 19) return !printf("-1\n");
for (int i = 0; i < 19; i++)
for (int j = 0; j < 19; j++)
for (int k = 0; k < N; k++) dp[i][j][k] = MOD;
for (int i = 1; i <= n; i++) {
dp[A[i]][0][i] = 0;
if (A[i]) dp[A[i] - 1][0][i] = 1;
}
for (int l = 1; l < 19; l++) {
for (int j = 0; j < 19; j++) {
for (int i = 1; i <= n; i++) {
if (i + (1 << l) > n + 1) continue;
dp[j][l][i] = dp[j][l - 1][i] + dp[j][l - 1][i + (1 << (l - 1))];
if (dp[j][l][i] > MOD) dp[j][l][i] = MOD;
if (j + 1 < 19) {
dp[j][l][i] = min(dp[j][l][i], dp[j + 1][l - 1][i] + dp[j + 1][l - 1][i + (1 << (l - 1))] + 1);
}
}
}
}
pd[0] = 0;
for (int i = 1; i <= n; i++) {
int pw = 0;
pd[i] = MOD;
for (; i - (1 << pw) >= 0; pw++) {
pd[i] = min(pd[i], pd[i - (1 << pw)] + dp[0][pw][i - (1 << pw) + 1]);
}
}
printf("%d\n", pd[n] >= MOD ? -1 : pd[n]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |