Submission #1179050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179050		kl_2200100003	Palembang Bridges (APIO15_bridge)	C++17	Compilation error	0 ms	0 KiB

bridge

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

typedef long long ll;

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

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

    vector<ll> cross_needs;
    ll total = 0;

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

        char P = a[0];
        ll S = stoll(a.substr(1));
        char Q = b[0];
        ll T = stoll(b.substr(1));

        if (P == Q) {
            total += abs(S - T);
        } else {
            cross_needs.push_back(S + T);
        }
    }

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

    sort(cross_needs.begin(), cross_needs.end());
    int M = cross_needs.size();

    if (K == 1) {
        ll median = cross_needs[M / 2];
        ll bridge_cost = 0;
        for (ll val : cross_needs) {
            bridge_cost += abs(val - median);
        }
        total += bridge_cost + M; // +1 per person crossing river
        cout << total << '\n';
        return 0;
    }

    // K == 2 case
    ll result = LLONG_MAX;

    for (int split = 0; split <= M; ++split) {
        ll left_cost = 0, right_cost = 0;

        if (split > 0) {
            ll median = cross_needs[split / 2];
            for (int i = 0; i < split; ++i) {
                left_cost += abs(cross_needs[i] - median);
            }
        }

        if (split < M) {
            int len = M - split;
            ll median = cross_needs[split + len / 2];
            for (int i = split; i < M; ++i) {
                right_cost += abs(cross_needs[i] - median);
            }
        }

        result = min(result, left_cost + right_cost);
    }

    total += result + M; // +1 per crossing citizen
    cout << total << '\n';
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:57:17: error: 'LLONG_MAX' was not declared in this scope
   57 |     ll result = LLONG_MAX;
      |                 ^~~~~~~~~
bridge.cpp:6:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    5 | #include <cmath>
  +++ |+#include <climits>
    6 | using namespace std;