#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define unint unsigned int
#define sint short int
#define usint unsigned short int
#define ll long long
#define ld long double
#define vt vector
#define pb push_back
#define mp make_pair
#define PI 3.14159265358979323
#define F first
#define S second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)a.size())
#define clr(x,a) memset(x, a, sizeof(x))
#define len(a) ((int)a.length())
#define E 2.7182818284590452353602874713527
#define FOR(i, x) for(int i=0; i<x; ++i)
#define For(i, x) for(auto& i: x)
#define RFOR(i, x) for(int i=x-1; i>=0; --i)
#define FORS(x, s, e, n) for(int x=s; x<=e; x+=n)
#define int long long
typedef pair<int, int> pii;
void solve(){
}
int32_t main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
int a;
cin >> a;
set<int>s;
int temp;
priority_queue<pii>pq;
set<ll>::iterator low;
int arr[a];
for(int x=0;x<a;x++){
cin >> temp;
arr[x]=temp;
s.insert(x);
pq.push(make_pair(temp,x));
}
int counter=0;
for(int x=0;x<(a+1)/2LL;x++){
pii cur=pq.top();
pq.pop();
while(s.find(cur.second)==s.end()&&!pq.empty()){
cur=pq.top();
pq.pop();
}
counter+=cur.first;
cout << counter << "\n";
// cout << "amos" << " " << cur.first << "\n";
int lefttarget=cur.second;
bool hayden=true;
low=s.lower_bound(lefttarget);
if(low==s.begin()){
hayden=false;
}
low--;
int leftind=*low;
int righttarget=cur.second+1;
int rightind=*s.lower_bound(righttarget);
// cout << leftind << " " << rightind << "-<\n";
if(s.find(leftind)!=s.end()){
s.erase(leftind);
}
if(s.find(rightind)!=s.end()){
s.erase(rightind);
}
// s.erase(s.find(leftind));
// s.erase(s.find(rightind));
int neighbour=0;
if(leftind>=0&&leftind<a&&hayden){
neighbour+=arr[leftind];
}
if(rightind<a){
neighbour+=arr[rightind];
}
// cout << " " << neighbour << " " << cur.first << " " << neighbour-cur.first << "$\n";
arr[cur.second]=neighbour-cur.first;
pq.push(make_pair(neighbour-cur.first,cur.second));
// for(auto it:s){
// cout << it << " ";
// }
// cout << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
