This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, a[500010], pre[500100], suf[500100];
int main () {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
bool y = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i > 1 and a[i] < a[i - 1]) y = 0;
}
if (y) {
cout << "0\n";
return 0;
}
for (int i = 0; i <= n; i++) pre[i] = suf[i] = INT_MAX / 3;
pre[0] = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == -1) pre[i] = pre[i - 1];
if (i > 1 and a[i] == 1 and a[i - 1] == 1) pre[i] = min(pre[i], pre[i - 2] + 1);
}
suf[0] = 0;
for (int i = 1; i <= n; i++) {
int j = n + 1 - i;
if (a[j] == 1) suf[i] = suf[i - 1];
if (i > 1 and a[j] == -1 and a[j + 1] == -1) suf[i] = min(suf[i], suf[i - 2] + 1);
}
int ans = INT_MAX / 2;
for (int i = 0; i <= n; i++) ans = min(ans, suf[i] + pre[n - i]);
if (ans > n * 5) ans = -1;
cout << ans << '\n';
return 0;}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |