Submission #388815

#	Time	Username	Problem	Language	Result	Execution time	Memory
388815		phathnv	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	111 ms	6020 KiB

bridge

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

typedef long long ll;

const int N = 1e5 + 7;
const int INF = 1e9 + 7;

struct Person{
    int a, b;
    bool operator < (const Person &oth){
        return a + b < oth.a + oth.b;
    }
};

struct TwoPQ{
    ll sumLeft, sumRight;
    priority_queue<int> Left;
    priority_queue<int, vector<int>, greater<int>> Right;
    void init(){
        sumLeft = sumRight = 0;
        while (!Left.empty())
            Left.pop();
        while (!Right.empty())
            Right.pop();
        Left.push(-INF);
        Right.push(INF);
    }
    void insert(int a, int b){
        Left.push(a), sumLeft += a;
        Right.push(b), sumRight += b;
        while (Left.top() > Right.top()){
            int l = Left.top();
            int r = Right.top();
            Left.pop(), sumLeft -= l;
            Right.pop(), sumRight -= r;
            Left.push(r), sumLeft += r;
            Right.push(l), sumRight += l;
        }
    }
    ll solve(){
        return sumRight - sumLeft;
    }
} twoPq;

int k, n;
Person a[N];
ll l[N], r[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> k >> n;
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        char x, y;
        cin >> x >> a[i].a >> y >> a[i].b;
        if (x == y){
            sum += abs(a[i].a - a[i].b);
            i--;
            n--;
        } else {
            sum++;
        }
    }
    sort(a + 1, a + 1 + n);

    twoPq.init();
    for(int i = 1; i <= n; i++){
        twoPq.insert(a[i].a, a[i].b);
        l[i] = twoPq.solve();
    }
    twoPq.init();
    for(int i = n; i >= 1; i--){
        twoPq.insert(a[i].a, a[i].b);
        r[i] = twoPq.solve();
    }

    if (k == 1){
        cout << sum + l[n];
    } else {
        ll res = 1e18;
        for(int i = 0; i <= n; i++)
            res = min(res, l[i] + r[i + 1]);
        cout << res + sum;
    }

    return 0;
}

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