Submission #549748

#	Time	Username	Problem	Language	Result	Execution time	Memory
549748		Jomnoi	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	48 ms	3496 KiB

bridge

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

const int MAX_N = 1e5 + 10;
const int INF = 1e9 + 7;

long long pre[MAX_N];
long long suml, sumr;
priority_queue <int> pql;
priority_queue <int, vector <int>, greater <int>> pqr;

void add(const int &v) {
    int median = INF;
    if(!pql.empty()) {
        median = pql.top();
    }

    if(v <= median) {
        suml += v;
        pql.push(v);
    }
    else {
        sumr += v;
        pqr.push(v);
    }

    if(pql.size() > pqr.size() + 1) {
        pqr.push(pql.top());
        sumr += pql.top();
        suml -= pql.top();
        pql.pop();
    }
    else if(pql.size() < pqr.size()) {
        pql.push(pqr.top());
        sumr -= pqr.top();
        suml += pqr.top();
        pqr.pop();
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int K, N;
    cin >> K >> N;
    vector <pair <int, int>> vec({make_pair(-INF, -INF)});
    long long same_side = 0;
    for(int i = 1; i <= N; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if(p == q) {
            same_side += abs(s - t);
        }
        else {
            vec.emplace_back(s, t);
        }
    }

    sort(vec.begin(), vec.end(), [&](const pair <int, int> &a, const pair <int, int> &b) {
        return a.first + a.second < b.first + b.second;
    });

    N = vec.size() - 1;
    same_side += N;
    for(int i = 1; i <= N; i++) {
        add(vec[i].first), add(vec[i].second);
        pre[i] = sumr - suml;
    }

    long long ans = pre[N];

    if(K == 2) {
        suml = sumr = 0;
        for(int i = N; i >= 1; i--) {
            add(vec[i].first), add(vec[i].second);
            ans = min(ans, pre[i - 1] + sumr - suml);
        }
    }

    cout << ans + same_side;
    return 0;
}

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