제출 #957572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957572		12345678	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	81 ms	9356 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e5+5;

#define ll long long

ll k, n, b[nx], d[nx], cnt, res, dpl[nx], dpr[nx], sml, smr, ans=LLONG_MAX;
char a[nx], c[nx];
vector<pair<ll, ll>> v(nx);
priority_queue<ll> pql;
priority_queue<ll, vector<ll>, greater<ll>> pqr;

void insert(int x)
{
    if (pql.empty()||(x<=pql.top())) pql.push(x), sml+=x;
    else pqr.push(x), smr+=x;
}

void adjust()
{
    while (pql.size()>pqr.size()) sml-=pql.top(), pqr.push(pql.top()), pql.pop(), smr+=pqr.top();
    while (pqr.size()>pql.size()) smr-=pqr.top(), pql.push(pqr.top()), pqr.pop(), sml+=pql.top();
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>k>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        if (a[i]==c[i]) res+=abs(b[i]-d[i]);
        else res++, v[++cnt]={b[i]+d[i], i};
    }
    sort(v.begin()+1, v.begin()+cnt+1);
    //for (int i=1; i<=cnt; i++) cout<<v[i].first<<' '<<v[i].second<<'\n';
    for (int i=1; i<=cnt; i++)
    {
        insert(b[v[i].second]);
        insert(d[v[i].second]);
        adjust();
        dpl[i]=smr-sml;
    }
    if (k==1) return cout<<dpl[cnt]+res, 0;
    while (!pql.empty()) pql.pop(), pqr.pop();
    sml=smr=0;
    for (int i=cnt; i>=1; i--)
    {
        insert(b[v[i].second]);
        insert(d[v[i].second]);
        adjust();
        dpr[i]=smr-sml;
    }
    for (int i=0; i<=cnt; i++) ans=min(ans, dpl[i]+dpr[i+1]+res);
    cout<<ans;
}

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