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;
for (int i = 1; i <= n; i++) cin >> a[i];
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 = suf[0] + pre[n];
for (int i = 1; i <= n; i++) ans = min(ans, suf[i - 1] + 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... |