제출 #739151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739151		Alihan_8	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	256 ms	14348 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int k, n; cin >> k >> n;
    vector <pair<int,int>> p;
    int res = 0;
    for ( int i = 0; i < n; i++ ){
        char a, b;
        int x, y;
        cin >> a >> x >> b >> y;
        if ( x > y ) swap(x, y);
        if ( a == b ){
            res += y - x;
        }
        else{
            p.pb({x, y});
        }
    }
    res += (int)p.size();
    sort(all(p), [&](pair <int,int> &x, pair <int,int> &y){
         return x.first + x.second < y.first + y.second;
    });
    multiset <int> L, R;
    int ls = 0, rs = 0;
    const int inf = 1e16 + 1;
    auto ins = [&](int x){
        int Mx = L.empty() ? inf : *L.rbegin();
        if ( x <= Mx ){
            L.insert(x);
            ls += x;
        }
        else{
            R.insert(x);
            rs += x;
        }
        while ( (int)L.size() > (int)R.size() ){
            auto l = prev(L.end());
            L.erase(l); ls -= *l;
            R.insert(*l); rs += *l;
        }
        while ( (int)R.size() > (int)L.size() ){
            auto r = R.begin();
            R.erase(r); rs -= *r;
            L.insert(*r); ls += *r;
        }
        return rs - ls;
    };
    n = (int)p.size();
    vector <int> pref(n + 1);
    for ( int i = 0; i < n; i++ ){
        auto [l, r] = p[i];
        ins(l);
        pref[i + 1] = ins(r);
    }
    int ans = pref.back();
    if ( k == 2 ){
        L.clear(), R.clear();
        ls = rs = 0;
        for ( int i = n - 1; i >= 0; i-- ){
            auto [l, r] = p[i];
            ins(l);
            chmin(ans, ins(r) + pref[i]);
        }
    }
    cout << ans + res;

    cout << '\n';
}
/*

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

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