Submission #827043

#	Time	Username	Problem	Language	Result	Execution time	Memory
827043		rinho	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	168 ms	13580 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

const int Nmax = 3e5;

int n, k, len;
long long ans = 0, suml = 0, sumr = 0, pre[Nmax + 3];
vector<pair<int, int>> val;
multiset<int> up, down;

bool cmp(pair<int, int> x, pair<int, int> y){
    return x.first + x.second < y.first + y.second;
}

void ins(int x){
    int med;
    if(down.size()) med = *down.rbegin();
    else med = 1e9 + 7;

    if(med < x){
        up.insert(x);
        sumr += 0ll + x;
    } else{
        down.insert(x);
        suml += 0ll + x;
    }

    if(down.size() > up.size() + 1){
        up.insert(*down.rbegin());
        sumr += 0ll + *down.rbegin();
        suml -= 0ll + *down.rbegin();
        down.erase(down.find(*down.rbegin()));
        return;
    }

    if(up.size() > down.size()){
        down.insert(*up.begin());
        suml += 0ll + *up.begin();
        sumr -= 0ll + *up.begin();
        up.erase(up.find(*up.begin()));
    }
}

void in(){
    cin >> k >> n;
    val.push_back({0, 0});
    for(int i = 1; i <= n; i++){
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if(p == q) ans += 0ll + abs(s - t);
        else val.push_back({s, t});
    }
    sort(val.begin(), val.end(), cmp);
    len = val.size() - 1;
}

void sol(){
    ans += 0ll + len;

    for(int i = 1; i <= len; i++){
        ins(val[i].first);
        ins(val[i].second);
        pre[i] = sumr - suml;
    }

    long long res = pre[len];

    if(k == 2){
        up.clear();
        down.clear();
        sumr = suml = 0;

        for(int i = len; i >= 1; i--){
            ins(val[i].first);
            ins(val[i].second);
            res = min(res, sumr - suml + pre[i - 1]);
        }
    }
    cout << ans + res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    in();
    sol();
    return 0;
}

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