Submission #1201676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201676		hackstar	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	172 ms	20800 KiB

bridge

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

using ll = long long;

struct median{
    multiset<int, greater<int> > low;
    multiset<int> high;
    ll sum_low = 0, sum_hight = 0;
    void add(int x){
        if(low.empty() || *low.begin() > x){
            low.insert(x);
            sum_low += x;
        }
        else{
            high.insert(x);
            sum_hight += x;
        }
        
        while(low.size() > high.size() + 1){
            int v = *low.begin();
            low.erase(low.begin());
            high.insert(v);
            sum_low -= v;
            sum_hight += v;
        }
        while(low.size() < high.size()){
            int v = *high.begin();
            high.erase(high.begin());
            low.insert(v);
            sum_low += v;
            sum_hight -= v;
        }
    }
    ll sum_median(){
        return low.empty() ? 0 : 1LL * *low.begin() * low.size() - sum_low + sum_hight - 1LL * *low.begin() * high.size();
    }
};

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> k >> n;
    vector<pair<int, int> > a;
    ll temp = 0, res = 0;
    char c1, c2;
    for(int i = 0, s, f; i < n; ++ i){
        cin >> c1 >> s >> c2 >> f;
        if(s > f) swap(s, f);
        if(c1 == c2) temp += f - s;
        else{
            temp ++;
            a.emplace_back(s, f);
        }
    }
    n = (int)a.size();
    if(n == 0){
        cout << temp;
        return 0;
    }
    sort(a.begin(), a.end(), [&](pair<int, int>r, pair<int,int>l){return r.first + r.second < l.first + l.second;});
    vector<ll> pref(n);
    median md;
    for(int i = 0; i < n; ++ i){
        md.add(a[i].first);
        md.add(a[i].second);
        pref[i] = md.sum_median();
    }
    res = pref.back();
    if(k == 2){
        median dm;
        for(int i = n - 1; i > 0; -- i){
            dm.add(a[i].first);
            dm.add(a[i].second);
            res = min(res, dm.sum_median() + pref[i-1]);
        }
    }
    res += temp;
    cout << res;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37