제출 #1281375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281375		Faisal_Saqib	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	82 ms	8808 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
priority_queue<ll> lt; // we will need to pop the maximum
priority_queue<ll,vector<ll>,greater<ll>> rt;
ll med=-1,lsm=0,rsm=0;
void add(int x)
{
    if(med==-1)
    {
        med=x;
        return;
    }
    if(x<=med)
    {
        lt.push(x);
        lsm+=x;
    }
    else
    {
        rt.push(x);
        rsm+=x;
    }
    if(lt.size()+1 < rt.size())
    {
        // right has more elements
        ll y=rt.top();
        rt.pop();
        rsm-=y;

        swap(y,med);

        lsm+=y;
        lt.push(y);
    }
    if(rt.size()+1 < lt.size())
    {
        ll y=lt.top();
        lt.pop();
        lsm-=y;

        swap(y,med);

        rsm+=y;
        rt.push(y);
    }
    // x+1 x
    // x x
    // x+1 x-1
}
long long getsum()
{
    return 1ll*lt.size()*med - lsm + rsm - 1ll*rt.size()*med;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k,n;
    cin>>k>>n;
    ll ans=0;
    vector<ll> tp;
    pair<ll,ll> b[n+1]={};
    vector<pair<ll,ll>> a;
    for(int i=0;i<n;i++)
    {
        char c,p;
        int x,y;
        cin>>c>>x>>p>>y;
        if(x>y)swap(x,y);
        if(c==p)
        {
            ans+=y-x;
        }
        else
        {
            ans+=1;
            tp.pb(x);
            tp.pb(y);
            b[i].first=x;
            b[i].second=y;
            a.pb({x+y,i});
        }
    }
    int sz=tp.size();
    if(!sz)
    {
        cout<<ans<<endl;
        return 0;
    }
    sort(begin(tp),end(tp));
    sort(begin(a),end(a));
    if(k==1)
    {
        for(auto i:tp)
        {
            ans+=abs(tp[sz/2]-i);
        }
        cout<<ans<<endl;
        return 0;
    }

    sz=a.size();
    vector<long long> pre(sz+1);
    for(int i=0;i<sz;i++)
    {
        add(b[a[i].second].first);
        add(b[a[i].second].second);
        pre[i+1]=getsum();
    }
    med=-1;
    lsm=0,rsm=0;
    while(lt.size())lt.pop();
    while(rt.size())rt.pop();
    ll mi=1e18;
    for(int i=sz-1;i>=0;i--)
    {
        add(b[a[i].second].first);
        add(b[a[i].second].second);
        mi=min(mi,getsum()+pre[i]);
    }
    cout<<ans+mi<<endl;
}

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