#include <bits/stdc++.h>
#define endl "\n"
#define upgrade ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
struct candy {
ll candy;
ll left;
ll right;
ll check;
};
// 백업==사탕
int main() {
ll n;
cin >> n;
// ll t = (n + 1) / 2;
vector<candy>arr(n+10);
priority_queue<pair<ll, ll>>pq;
for (int i = 1; i <= n; i++) {
cin >> arr[i].candy;
pq.push({ arr[i].candy,i });
arr[i].left = i - 1;
arr[i].right = i + 1;
arr[i].check = 0;
}
arr[0].candy = -1;
arr[0].candy = 0;
arr[n + 1].candy = -1;
arr[n + 1].check = 0;
ll ans = 0;
for (int i = 0; i < (n + 1) / 2; i++) {
while (arr[pq.top().second].check) {
pq.pop();
}
pair<ll, ll>save{ pq.top().first,pq.top().second };
pq.pop();
arr[arr[save.second].left].check = 1;
arr[arr[save.second].right].check = 1;
ans += save.first;
cout << ans << endl;
arr[save.second].candy = arr[arr[save.second].left].candy + arr[arr[save.second].right].candy - arr[save.second].candy;
pq.push({ arr[save.second].candy,save.second });
arr[save.second].left = arr[arr[save.second].left].left;
arr[arr[save.second].left].right = save.second;
arr[save.second].right = arr[arr[save.second].right].right;
arr[arr[save.second].right].left = save.second;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
