Submission #1149744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149744		irmuun	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	67 ms	7348 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

priority_queue<ll>L;
priority_queue<ll,vector<ll>,greater<ll>>R;
ll sumL=0,sumR=0;

void add(ll x){
    ll med=(L.empty()?(ll)1e9:L.top());
    if(x<=med){
        L.push(x);
        sumL+=x;
    }
    else{
        R.push(x);
        sumR+=x;
    }
    if(L.size()<R.size()){
        ll y=R.top();
        R.pop();
        L.push(y);
        sumL+=y;
        sumR-=y;
    }
    else if(L.size()>R.size()+1){
        ll y=L.top();
        L.pop();
        R.push(y);
        sumR+=y;
        sumL-=y;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll K,n;
    cin>>K>>n;
    vector<array<ll,3>>v;
    ll same=0;
    for(ll i=1;i<=n;i++){
        char p,q;
        ll a,b;
        cin>>p>>a>>q>>b;
        if(p==q){
            same+=abs(a-b);
        }
        else{
            v.pb({a+b,a,b});
        }
    }
    sort(all(v));
    ll ans=0;
    ll m=v.size();
    ll pre[m+5],suf[m+5];
    pre[0]=0;
    for(ll i=0;i<m;i++){
        add(v[i][1]);
        add(v[i][2]);
        pre[i+1]=sumR-sumL;
    }
    ans=pre[m];
    if(K==2){
        while(!L.empty()) L.pop();
        while(!R.empty()) R.pop();
        sumL=sumR=0;
        // L.clear();
        // R.clear();
        suf[m]=0;
        for(ll i=m-1;i>=1;i--){
            add(v[i][1]);
            add(v[i][2]);
            suf[i]=sumR-sumL;
            ans=min(ans,pre[i]+suf[i]);
        }
    }
    cout<<ans+same+m;
}

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