Submission #1179053

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

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits> // For LLONG_MAX
using namespace std;

typedef long long ll;

struct Person {
    char fromZone, toZone;
    int fromPos, toPos;
};

ll distance(const Person& p, int bridgePos) {
    if (p.fromZone == p.toZone) {
        return abs(p.fromPos - p.toPos);
    } else {
        return abs(p.fromPos - bridgePos) + 1 + abs(p.toPos - bridgePos);
    }
}

ll totalDistance(const vector<Person>& people, const vector<int>& bridges) {
    ll sum = 0;
    for (const auto& p : people) {
        if (p.fromZone == p.toZone) {
            sum += abs(p.fromPos - p.toPos);
        } else {
            ll minDist = LLONG_MAX;
            for (int b : bridges) {
                minDist = min(minDist, distance(p, b));
            }
            sum += minDist;
        }
    }
    return sum;
}

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

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

    vector<Person> people(N);
    vector<int> candidateBridges;

    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        people[i].fromZone = s[0];
        int idx = 1;
        while (isdigit(s[idx])) idx++;
        people[i].fromPos = stoi(s.substr(1, idx - 1));
        people[i].toZone = s[idx];
        people[i].toPos = stoi(s.substr(idx + 1));

        if (people[i].fromZone != people[i].toZone) {
            candidateBridges.push_back(people[i].fromPos);
            candidateBridges.push_back(people[i].toPos);
        }
    }

    sort(candidateBridges.begin(), candidateBridges.end());
    candidateBridges.erase(unique(candidateBridges.begin(), candidateBridges.end()), candidateBridges.end());

    ll result = LLONG_MAX;
    int m = candidateBridges.size();

    // Try all combinations of up to K bridges (K <= 2)
    if (K == 1) {
        for (int i = 0; i < m; ++i) {
            vector<int> bridges = {candidateBridges[i]};
            result = min(result, totalDistance(people, bridges));
        }
    } else {
        for (int i = 0; i < m; ++i) {
            for (int j = i; j < m; ++j) {
                vector<int> bridges = {candidateBridges[i], candidateBridges[j]};
                result = min(result, totalDistance(people, bridges));
            }
        }
    }

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

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