Submission #1206113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206113		rcll	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	104 ms	3512 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool cmp(pair<int,int> a,pair<int,int> b) {
    return a.first+a.second<b.first+b.second;
}

priority_queue<int> lpq;
priority_queue<int,vector<int>,greater<int>> rpq;
ll lsum,rsum;

void insert(int x) {
    int median=(lpq.size() ? lpq.top() : 1000000001);
    if (x <= median) {
        lpq.push(x);
        lsum+=x;
    } else {
        rpq.push(x);
        rsum+=x;
    }
    if (rpq.size()+1<lpq.size()) {
        int nxt=lpq.top();
        lpq.pop();
        rpq.push(nxt);
        lsum-=nxt;
        rsum+=nxt;
    } else if (lpq.size()<rpq.size()) {
        int nxt=rpq.top();
        rpq.pop();
        lpq.push(nxt);
        rsum-=nxt;
        lsum+=nxt;
    }
}

ll pref[100001];

int main() {
    int k,n;
    ll same_side=0;
    vector<pair<int,int>> v={{0,0}};
    cin >> k >> n;
    for (int i=0; i<n; i++) {
        char a,b;
        int x,y;
        cin >> a >> x >> b >> y;
        if (a==b) {
            same_side+=abs(x - y);
        } else {
            v.push_back({x,y});
        }
    }
    sort(v.begin(),v.end(),cmp);
    n=v.size() - 1;
    same_side+=n;
    lsum=rsum=0;
    for (int i=1; i<=n; i++) {
        insert(v[i].first);
        insert(v[i].second);
        pref[i]=rsum - lsum;
    }
    ll ans=pref[n];
    if (k==2) {
        while (lpq.size()) {
            lpq.pop();
        }
        while (rpq.size()) {
            rpq.pop();
        }
        lsum=rsum=0;
        for (int i=n; i; i--) {
            insert(v[i].first);
            insert(v[i].second);
            ans=min(ans,rsum-lsum+pref[i -1]);
        }
    }
    cout << same_side+ans;
    return 0;
}

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