Submission #64590473

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> vec(n + 1);
    for(int i = 1; i <= n; i++) cin >> vec[i];
    multiset<ll> sa, sb;
    vector<ll> pre(n + 1), suf(n + 2), pres(n + 1);
    for(int i = 1; i <= n; i++) pres[i] = pres[i - 1] + vec[i];
    ll now = 0;
    for(int i = 2; i <= n; i += 2){
        ll a = vec[i - 1], b = vec[i];
        if(a > b) swap(a, b);
        if(sa.empty()){
            now += b;
            sa.insert(a);
            sb.insert(b);
            continue;
        }
        if(a > (*sb.begin())){
            now -= (*sb.begin());
            sa.insert(*sb.begin());
            sb.erase(sb.begin());
            now += a + b;
            sb.insert(a);
            sb.insert(b);
        }
        else if(b < (*prev(sa.end()))){
            now += (*prev(sa.end()));
            sb.insert(*prev(sa.end()));
            sa.erase(prev(sa.end()));
            sa.insert(a);
            sa.insert(b);
        }
        else{
            now += b;
            sa.insert(a);
            sb.insert(b);
        }
        pre[i] = now - pres[i] + now;
    }
    multiset<ll>().swap(sa);
    multiset<ll>().swap(sb);
    now = 0;
    for(int i = n; i > 1; i -= 2){
        ll a = vec[i - 1], b = vec[i];
        if(a > b) swap(a, b);
        if(sa.empty()){
            sa.insert(a);
            sb.insert(b);
            now += b;
            continue;
        }
        if(a > (*sb.begin())){
            now -= (*sb.begin());
            sa.insert(*sb.begin());
            sb.erase(sb.begin());
            now += a + b;
            sb.insert(a);
            sb.insert(b);
        }
        else if(b < (*prev(sa.end()))){
            now += (*prev(sa.end()));
            sb.insert(*prev(sa.end()));
            sa.erase(prev(sa.end()));
            sa.insert(a);
            sa.insert(b);
        }
        else{
            now += b;
            sa.insert(a);
            sb.insert(b);
        }
        suf[i - 1] = now - (pres[n] - pres[i - 2] - now);
        //cout << i - 1 << " " << suf[i - 1] << "\n";
    }
    ll ans = 0;
    if(n & 1){
        for(int i = 1; i <= n; i += 2){
            ans = max(ans, pre[i - 1] + suf[i + 1]);
        }
    }
    else ans = pre[n];
    cout << ans << "\n";
}

Submission Info

Judge Result