#include<bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
using namespace std;
void solve() {
int n;
cin >> n;
long long a[n];
set<pair<long long,long long>> s, s1;
for(int i = 0;i<n;i++){
cin >> a[i];
s.insert({a[i], i});
s1.insert({i, a[i]});
}
long long sum=0;
for(int i = 1;i<=(n+1)/2;i++) {
// for(auto j:s)cout << j.first << " " << j.second << "\n";
// cout <<"\n";
long long mx;
int idx;
mx=(*(--s.end())).first;
idx=(*(--s.end())).second;
sum+=mx;
s.erase({mx, idx});
s1.erase({idx, mx});
auto it1=s1.lower_bound({idx+1, 0});
auto it2=it1;
if(s.size()) {
if(it1==s1.end() or it1==s1.begin()) {
if(it1==s1.end())--it1;
int val=(*it1).second;
s.erase({(*it1).second, (*it1).first});
s1.erase(it1);
s.insert({val-mx, idx});
s1.insert({idx,val-mx});
}
else {
it2--;
long long sm=(*it1).second+(*it2).second-mx;
s.erase({(*it2).second, (*it2).first});
s1.erase(it2);
s.erase({(*it1).second, (*it1).first});
s1.erase(it1);
s.insert({sm, idx});
s1.insert({idx, sm});
}
}
cout << sum << "\n";
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int t=1;
while(t--)solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
