Submission #4024512

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
const ll INF = 5e15;
const ll MOD = 1e9 + 7;

ll N;

struct Cost {
    ll cost;
    ll idx;
    bool A;
    Cost(ll c, ll i, bool A) : cost(c), idx(i), A(A) {}
};

bool valid(const set<ll> &SA, const set<ll> &SB){
    if(SA.empty() || SB.empty()) return true;
    set<ll> tmp;
    for(ll e : SA) tmp.insert(e);
    for(ll e : SB) tmp.insert(e);
    return tmp.size() != N;
}

int main(){
    cin >> N;
    vector<Cost> v;
    for(ll i = 0; i < N; i++){
        ll a, b;
        cin >> a >> b;
        v.push_back(Cost(a, i, true));
        v.push_back(Cost(b, i, false));
    }
    sort(v.begin(), v.end(), [](const auto &a, const auto &b){ return a.cost < b.cost; });
    set<ll> SA, SB;
    ll ans = 0;
    for(ll i = 0; i < N; i++){
        (v[i].A ? SA : SB).insert(v[i].idx);
        ans += v[i].cost;
    }
    if(!valid(SA, SB)){
        if(v[N - 1].idx != v[N].idx){
            ans -= v[N - 1].cost;
            ans += v[N].cost;
        }else{
            ll v1 = v[N].cost - v[N - 2].cost;
            ll v2 = v[N + 1].cost - v[N - 1].cost;
            ans += min(v1, v2);
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result