Submission #497870

#	Time	Username	Problem	Language	Result	Execution time	Memory
497870		clams	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	116 ms	13488 KiB

bridge

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

const int INF = 1e18;

int sumlow = 0, sumhigh = 0;
multiset<int> low, high;

void sinsert(int val) {
    int med = low.empty() ? INF : *low.rbegin();

    if (val > med) {
        high.insert(val);
        sumhigh += val;
    } else {
        low.insert(val);
        sumlow += val;
    }

    if (high.size() > low.size()) {
        int tmp = *high.begin();

        low.insert(tmp);
        sumlow += tmp;

        sumhigh -= tmp;
        high.erase(high.find(tmp));
    } else if (low.size() > high.size() + 1) {
        int tmp = *low.rbegin();

        high.insert(tmp);
        sumhigh += tmp;

        sumlow -= tmp;
        low.erase(low.find(tmp));
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k, n;
    cin >> k >> n;

    vector<pair<int, int>> diff;
    int same = 0;

    for (int i = 0; i < n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;

        if (p == q) {
            same += abs(s - t);
        } else {
            if (s > t) swap(s, t);
            diff.push_back({s, t});
        }
    }

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

    int sz = diff.size();
    same += sz; // crossing the river

    if (k == 1) {
        if (sz == 0) {
            cout << same;
            return 0;
        }

        for (int i = 0; i < sz; i++) {
            sinsert(diff[i].first);
            sinsert(diff[i].second);
        }

        int med = *low.rbegin();
        int ans = (med * (int)low.size() - sumlow) + (sumhigh - med * (int)high.size());

        cout << same + ans;
        return 0;
    }


}

/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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