Submission #1179048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179048		kl_2200100003	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2 ms	320 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

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

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

    vector<ll> same_zone;
    vector<ll> cross_values;

    for (int i = 0; i < N; ++i) {
        string p, q;
        cin >> p >> q;

        char Pi = p[0];
        ll Si = stoll(p.substr(1));
        char Qi = q[0];
        ll Ti = stoll(q.substr(1));

        if (Pi == Qi) {
            same_zone.push_back(abs(Si - Ti));
        } else {
            cross_values.push_back(Si + Ti);
        }
    }

    ll total = 0;
    for (ll d : same_zone) total += d;

    if (cross_values.empty() || K == 0) {
        total += cross_values.size();
        cout << total << '\n';
        return 0;
    }

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

    if (K == 1) {
        ll median = cross_values[cross_values.size() / 2];
        for (ll x : cross_values) {
            total += abs(x - 2 * (median / 2)) + 1;
        }
        cout << total << '\n';
        return 0;
    }
    int m = cross_values.size();
    vector<ll> prefix(m + 1), suffix(m + 1);

    for (int i = 0; i < m; ++i)
        prefix[i + 1] = prefix[i] + cross_values[i];
    for (int i = m - 1; i >= 0; --i)
        suffix[i] = suffix[i + 1] + cross_values[i];

    ll best = 1e18;

    for (int split = 0; split <= m; ++split) {
        // left [0, split - 1], right [split, m - 1]
        ll left_cost = 0;
        if (split > 0) {
            int mid = split / 2;
            ll median = cross_values[mid];
            for (int i = 0; i < split; ++i) {
                left_cost += abs(cross_values[i] - median);
            }
        }

        ll right_cost = 0;
        if (split < m) {
            int len = m - split;
            int mid = split + len / 2;
            ll median = cross_values[mid];
            for (int i = split; i < m; ++i) {
                right_cost += abs(cross_values[i] - median);
            }
        }

        best = min(best, left_cost + right_cost + m);
    }

    cout << total + best << '\n';
    return 0;
}

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