Submission #1312703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312703		btkhg	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	30 ms	5036 KiB

bridge

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

ll cost_one_bridge(const vector<pair<ll,ll>>& segs) {
    vector<ll> pts;
    for (auto &p : segs) {
        pts.push_back(p.first);
        pts.push_back(p.second);
    }
    sort(pts.begin(), pts.end());
    ll x = pts[pts.size()/2];

    ll cost = 0;
    for (auto &p : segs) {
        cost += abs(p.first - x) + abs(p.second - x) + 1;
    }
    return cost;
}

ll cost_group(const vector<pair<ll,ll>>& segs) {
    if (segs.empty()) return 0;
    vector<ll> pts;
    for (auto &p : segs) {
        pts.push_back(p.first);
        pts.push_back(p.second);
    }
    sort(pts.begin(), pts.end());
    ll x = pts[pts.size()/2];
    ll cost = 0;
    for (auto &p : segs) {
        cost += abs(p.first - x) + abs(p.second - x) + 1;
    }
    return cost;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K, N;
    cin >> K >> N;

    ll answer = 0;
    vector<pair<ll,ll>> cross;

    for (int i = 0; i < N; i++) {
        char P, Q;
        ll S, T;
        cin >> P >> S >> Q >> T;
        if (P == Q) {
            answer += llabs(S - T);
        } else {
            ll L = min(S, T);
            ll R = max(S, T);
            cross.push_back({L, R});
        }
    }

    if (cross.empty()) {
        cout << answer << "\n";
        return 0;
    }

    if (K == 1) {
        answer += cost_one_bridge(cross);
        cout << answer << "\n";
        return 0;
    }

    sort(cross.begin(), cross.end());

    int M = cross.size();
    vector<ll> pref(M+1), suff(M+2);

    vector<pair<ll,ll>> tmp;
    for (int i = 0; i < M; i++) {
        tmp.push_back(cross[i]);
        pref[i+1] = cost_group(tmp);
    }

    tmp.clear();
    for (int i = M-1; i >= 0; i--) {
        tmp.push_back(cross[i]);
        suff[i+1] = cost_group(tmp);
    }

    ll best = LLONG_MAX;
    for (int i = 0; i <= M; i++) {
        best = min(best, pref[i] + suff[i+1]);
    }

    answer += best;
    cout << answer << "\n";
}

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