Submission #1199968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199968		amanthaband	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	69 ms	4072 KiB

bridge

#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

using ll = long long;
ll mod = 1000000007;

ll modpow(ll a, ll b) {
    ll result = 1;
    a %= mod;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return result;
}

int main() {
    ll k, n;
    cin >> k >> n;
    vector<ll> home;
    vector<ll> office;
    ll sum_distance = 0;

    if (k == 1) {
        for (ll z = 0; z < n; z++) {
            char p, q;
            ll s, t;
            cin >> p >> s >> q >> t;
            if (p == q) {
                sum_distance += llabs(s - t);
            } else {
                home.push_back(s);
                office.push_back(t);
            }
        }
        if (home.size() == 0) {
            cout << sum_distance << endl;
            return 0;
        }
        vector<ll> positions;
        for (ll i = 0; i < home.size(); i++) {
            positions.push_back(home[i]);
            positions.push_back(office[i]);
        }
        sort(positions.begin(), positions.end());
        ll pos = positions[positions.size() / 2];
        ll ans = sum_distance;
        for (ll i = 0; i < home.size(); i++) {
            ans += llabs(home[i] - pos) + llabs(office[i] - pos) + 1;
        }
        cout << ans << endl;
    } else {
        vector<pair<ll, ll>> people;
        for (ll z = 0; z < n; z++) {
            char p, q;
            ll s, t;
            cin >> p >> s >> q >> t;
            if (p == q) {
                sum_distance += llabs(s - t);
            } else {
                people.push_back({s, t});
            }
        }
        if (people.size() == 0) {
            cout << sum_distance << endl;
            return 0;
        }
        sort(people.begin(), people.end());
        ll m = people.size();
        
        ll ans = 1e18;
        vector<ll> all_home, all_office;
        for (auto [h, o] : people) {
            all_home.push_back(h);
            all_office.push_back(o);
        }
        for (ll split = 1; split < m; split++) {
            vector<ll> left, right;
            for (ll i = 0; i < split; i++) {
                left.push_back(people[i].first);
                left.push_back(people[i].second);
            }
            for (ll i = split; i < m; i++) {
                right.push_back(people[i].first);
                right.push_back(people[i].second);
            }
            sort(left.begin(), left.end());
            sort(right.begin(), right.end());
            ll lpos = left[left.size() / 2];
            ll rpos = right[right.size() / 2];
            ll cost = sum_distance;
            for (ll i = 0; i < m; i++) {
                if (i < split) {
                    cost += llabs(people[i].first - lpos) + llabs(people[i].second - lpos) + 1;
                } else {
                    cost += llabs(people[i].first - rpos) + llabs(people[i].second - rpos) + 1;
                }
            }
            ans = min(ans, cost);
        }
        cout << ans << endl;
    }
    return 0;
}

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