이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define _ << " " <<
const int MAXN = 5e5 + 5;
const int off = 1 << 19;
const int inf = 1e9;
#define int long long
int a[MAXN];
int l[MAXN];
int r[MAXN];
int before[MAXN];
unordered_map<int, int> specialChair;
typedef pair<int, int> pii;
bool possible(multiset<int> s)
{
int last = -1, timer = 0;
for(auto x : s)
{
if(last == -1) {
timer += x;
}
else {
if (r[last] <= l[x])
timer += x - last;
else
timer += min(last - l[last] + x - l[last], r[last] - last + r[last] - x);
}
if(timer > 2 * (x)) {
return 0;
}
last = x;
}
return 1;
}
long long sum;
multiset<int> TT;
void solve(int x, int d, int type) {
int cnt = 0;
while(a[x] > 0) {
TT.insert(x);
if(possible(TT)) {
a[x] --;
sum --;
cnt ++;
}
else {
TT.erase(TT.find(x));
break;
}
}
}
int v[MAXN];
signed main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
v[i] = a[i];
if (a[i] != -1) sum += a[i];
}
int tmp = -inf;
for (int i = 0; i < n; ++i) {
if (a[i] == -1) {
tmp = i;
}
l[i] = tmp;
}
tmp = inf;
for (int i = n - 1; i >= 0; --i) {
if (a[i] == -1) {
tmp = i;
}
r[i] = tmp;
}
vector<pair<int, pii>> candidates;
for (int i = 0; i < n; ++i) {
if (a[i] > 0) {
if (r[i] != inf) {
candidates.push_back({r[i] - i, {i, 1}});
}
if (l[i] != -inf) {
candidates.push_back({i - l[i], {i, 0}});
}
}
}
sort(candidates.begin(), candidates.end());
for(int i = 0; i < n; i++) {
if(a[i] == -1) continue;
int p = i;
for(int j = i + 1; j < r[i]; j++) if(a[j] > 0 && (a[p] == 0 || min(r[j] - j, j - l[j])) < min(r[p] - p, p - l[p])) { p = j; }
if(a[p] == 0) { i = r[i]; continue; }
a[p]--;
TT.emplace(p);
i = r[i];
}
for (auto candidate : candidates) {
int x = candidate.second.first;
int d = candidate.first;
int type = candidate.second.second;
solve(x, d, type);
}
sum =0;
for(int i = 0; i < n; i++) sum += max(a[i], 0ll);
cerr << '\n';
cout << sum << '\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... |