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;
typedef long long ll;
int n, a[505050], l[505050], r[505050], s[505050];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] != -1) ans += a[i];
}
int p = -1, q = -1, y = -1;
for (int i = 1; i <= n; i++) {
if (a[i] == -1) p = i;
else if (p != -1) l[i] = p;
}
p = -1;
for (int i = n; i >= 1; i--) {
if (a[i] == -1) p = i;
else if (a[i]) {
if (p != -1) r[i] = p;
if (q != -1) s[i] = q; else y = i;
q = i;
}
}
map<int, int> mp;
priority_queue<int> pq;
ll sum = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= 0) continue;
int d = INT_MAX;
if (l[i]) d = min(d, 2 * (i - l[i]));
if (r[i]) d = min(d, 2 * (r[i] - i));
int f = d;
if (s[i] && r[i]) {
if (s[i] < r[i]) f = min(f, 2 * (r[i] - s[i]));
else f = 0;
}
if (i == y) f = 0;
--a[i];
while (a[i] && sum + (i - 1) <= 2 * (i - 1)) {
mp[d]++;
sum += d;
--a[i];
}
if (a[i]) {
if (prev(mp.end())->first >= d) {
mp[d] += a[i];
sum += 1ll * d * a[i];
}
while (!mp.empty() && sum + (i - 1) > 2 * (i - 1)) {
auto [a, b] = *prev(mp.end());
if (sum - 1ll * a * b + (i - 1) > 2 * (i - 1)) {
sum -= 1ll * a * b;
mp.erase(prev(mp.end()));
}else {
ll diff = sum + (i - 1) - 2 * (i - 1);
ll r = (diff - 1) / a;
sum -= 1ll * a * r; mp[a] -= r;
break;
}
}
}
if (sum + (i - 1) > 2 * (i - 1)) {
if (prev(mp.end())->first >= f) {
auto [a, b] = *prev(mp.end());
sum -= a;
if (--mp[a] == 0) mp.erase(prev(mp.end()));
sum += f; mp[f]++;
}
}else {
sum += f; mp[f]++;
}
}
for (auto [a, b] : mp) ans -= b;
cout << ans << '\n';
}
# | 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... |