#include <bits/stdc++.h>
using namespace std;
#define int long long
int solveTestCase(int test) {
int n;
cin >> n;
int a[n + 2] = {};
for (int i = 1; i <= n; i++) cin >> a[i];
int p1[n + 2] = {}, p2[n + 2] = {};
p1[1] = a[1];
for (int i = 2; i <= n; i++) {
if (i % 2)
p1[i] = a[i] + p1[i - 2];
else
p2[i] = a[i] + p2[i - 2];
}
set<pair<int, pair<int, int>>, decltype(greater<>())> s;
map<int, int> begin, end;
map<pair<int, int>, int> rev;
for (int i = 1; i <= n; i++) {
s.insert(make_pair(a[i], make_pair(i, i)));
begin[i] = i;
end[i] = i;
rev[{i, i}] = a[i];
}
int ans = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
auto temp = s.begin();
ans += temp->first;
cout << ans << "\n";
pair<int, int> next = temp->second;
end.erase(next.second);
begin.erase(next.first);
rev.erase(next);
auto it1 = begin.find(next.second + 1);
if (it1 != begin.end()) {
next.second = it1->second - 1;
s.erase(make_pair(rev[*it1], *it1));
rev.erase(*it1);
end.erase(it1->second);
begin.erase(it1);
}
auto it2 = end.find(next.first - 1);
if (it2 != end.end()) {
next.first = it2->second + 1;
s.erase(make_pair(rev[{it2->second, it2->first}], make_pair(it2->second, it2->first)));
rev.erase(*it2);
begin.erase(it2->first);
end.erase(it2);
}
if (next.second == n)
next.second--;
else
next.second++;
if (next.first == 1)
next.first++;
else
next.first--;
s.erase(temp);
assert((next.second - next.first) % 2 == 0 && next.second - next.first != 0);
int val = next.second % 2 ? p1[next.second] - p1[next.first] + a[next.first] - (p2[next.second - 1] - p2[next.first + 1] + a[next.first + 1]) : p2[next.second] - p2[next.first] + a[next.first] - (p1[next.second - 1] - p1[next.first + 1] + a[next.first + 1]);
s.insert(make_pair(val, next));
rev[next] = val;
begin.insert(next);
end[next.second] = next.first;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
//cin >> test;
for (int i = 1; i <= test; i++)
solveTestCase(i);
}
Compilation message
candies.cpp: In function 'long long int solveTestCase(long long int)':
candies.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
8 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
8 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
