제출 #1179037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179037		kl_2200100003	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	328 KiB

bridge

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

struct Citizen {
    int sideFrom, sideTo;
    ll from, to;
};

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

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

    vector<Citizen> citizens(N);
    vector<ll> bridge_candidates;

    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        citizens[i].sideFrom = (s[0] == 'A' ? 0 : 1);
        ll num1 = 0, j = 1;
        while (isdigit(s[j])) num1 = num1 * 10 + (s[j++] - '0');
        citizens[i].from = num1;

        citizens[i].sideTo = (s[j++] == 'A' ? 0 : 1);
        ll num2 = 0;
        while (j < s.size()) num2 = num2 * 10 + (s[j++] - '0');
        citizens[i].to = num2;

        if (citizens[i].sideFrom != citizens[i].sideTo) {
            // Add both positions for potential bridge
            bridge_candidates.push_back(citizens[i].from);
            bridge_candidates.push_back(citizens[i].to);
        }
    }

    sort(bridge_candidates.begin(), bridge_candidates.end());
    ll ans = LLONG_MAX;

    for (ll bridge : bridge_candidates) {
        ll total = 0;
        for (const auto& c : citizens) {
            if (c.sideFrom == c.sideTo) {
                total += abs(c.from - c.to);
            } else {
                // Cost using bridge at `bridge`
                ll temp = abs(c.from - bridge) + 1 + abs(c.to - bridge);
                total += temp;
            }
        }
        ans = min(ans, total);
    }

    cout << ans << '\n';
    return 0;
}

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