제출 #916708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916708		huantran	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	69 ms	14280 KiB

bridge

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

using namespace std;
typedef long long int ll;
const int maxn = 1e6 + 5;
const int INF = 1e9;
const ll inf = 1e18;

ll k, n;
vector<pair<ll, ll>> pos;
ll pre[maxn], suf[maxn];
priority_queue<ll> ql;
priority_queue<ll, vector<ll>, greater<ll>> qr;
ll suml = 0, sumr = 0;

void insert_queue(ll x)
{
    ll med;
    if(ql.size())   
        med = ql.top();
    else
        med = inf;

    if(x <= med)
        ql.push(x), suml += x;
    else    
        qr.push(x), sumr += x;

    if(ql.size() > qr.size() + 1)
    {
        ll t = ql.top();
        ql.pop(), suml -= t;
        qr.push(t), sumr += t;
    }
    else if(qr.size() > ql.size())
    {
        ll t = qr.top();
        qr.pop(), sumr -= t;
        ql.push(t), suml += t;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> k >> n;
    ll tol_dis = 0;
    for(int i = 1; i <= n; i++)
    {
        char a, b;
        ll x, y;
        cin >> a >> x >> b >> y;
        if(x > y)
            swap(x, y);
        if(a == b)
            tol_dis += (y - x);
        else
            pos.push_back({x, y});
    }

    tol_dis += (int)pos.size();
    sort(pos.begin(), pos.end(), [&](const pair<ll, ll> &a, const pair<ll, ll> &b){
        if((a.first + a.second) == (b.first + b.second))
            return a < b;
        return (a.first + a.second) < (b.first + b.second);
    });

    for(int i = 0; i < (int)pos.size(); i++)
    {
        insert_queue(pos[i].first);
        insert_queue(pos[i].second);
        pre[i] = sumr - suml;
    }
    while(!ql.empty())
        ql.pop();
    while(!qr.empty())
        qr.pop();

    sumr = suml = 0;
    for(int i = (int)pos.size() - 1; i >= 0; i--)
    {
        insert_queue(pos[i].first);
        insert_queue(pos[i].second);
        suf[i] = sumr - suml;
    }

    ll ans = pre[(int)pos.size() - 1];

    if(k == 2)
    {
        for(int i = 0; i < (int)pos.size(); i++)
            ans = min(ans, pre[i] + suf[i + 1]);
    }

    cout << ans + tol_dis;
    // for(int i = 0; i < (int)pos.size(); i++)
    //     cout << pre[i] << ' ';
    // for(int i = 0; i < (int)pos.size(); i++)
    // {
    //     cout << pos[i].first << ' ' << pos[i].second << '\n';
    // }
}

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