Submission #162281

#	Time	Username	Problem	Language	Result	Execution time	Memory
162281		rama_pang	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	588 ms	18508 KiB

bridge

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

lint solve(lint K, vector<pair<lint, lint>> A) {
    if (A.empty()) 
        return 0;

    lint N = A.size();
    vector<lint> points;
    sort(A.begin(), A.end(), [&](pair<lint, lint> l, pair<lint, lint> r) {
        return l.first + l.second < r.first + r.second;
    });

    auto running_median = [&](vector<pair<lint, lint>> A) {
        multiset<lint> sml;
        multiset<lint> big;
        lint sum_sml = 0, sum_big = 0;
        vector<lint> res(N + 1, 0);

        for (int i = 1; i <= N; i++) {
            sml.emplace(A[i - 1].first);
            sum_sml += A[i - 1].first;
            big.emplace(A[i - 1].second);
            sum_big += A[i - 1].second;

            while (*sml.rbegin() > *big.begin()) {
                sum_sml += *big.begin() - *sml.rbegin();
                sum_big += *sml.rbegin() - *big.begin();
                big.emplace(*sml.rbegin());
                sml.emplace(*big.begin());
                sml.erase(prev(sml.end()));
                big.erase(big.begin());
            }

            res[i] = sum_big - sum_sml;
        }

        return res;
    };

    vector<lint> prefix_median = running_median(A);
    reverse(A.begin(), A.end());
    vector<lint> suffix_median = running_median(A);
    reverse(A.begin(), A.end());

    lint res = INT64_MAX;

    for (int cur = 0; cur <= N; cur++) {
        res = min(res, prefix_median[cur] + suffix_median[N - cur]);
    }

    if (K == 1)
        res = prefix_median[N];

    return res;
}

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

    lint K, N, ans = 0;
    vector<pair<lint, lint>> A;

    cin >> K >> N;

    for (int i = 0; i < N; i++) {
        char Z1, Z2;
        lint B1, B2;

        cin >> Z1 >> B1 >> Z2 >> B2;
        if (B1 > B2) swap(B1, B2);
        if (Z1 == Z2)
            ans += B2 - B1;
        else
            A.emplace_back(B1, B2);
    }

    cout << ans + A.size() + solve(K, A) << "\n";

    return 0;
}

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