Submission #521403

#	Time	Username	Problem	Language	Result	Execution time	Memory
521403		Sharky	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2053 ms	8276 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
#define sz(x) x.size()
#define pq priority_queue
int pref[N], suff[N];
bool cmp(pair<int, int> x, pair<int, int> y) {
    return x.first + x.second < y.first + y.second;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int sameside = 0, k, n, m = 0, ans = 0; cin >> k >> n;
    vector<pair<int, int> > pv; pv.push_back({0, 0});
    vector<int> v(2 * n + 5);
    for (int i = 1; i <= n; i++) {
        char p, q; int s, t; cin >> p >> s >> q >> t;
        if (p == q) sameside += abs(s - t);
        else {
            if (s > t) swap(s, t);
            m++; v[m] = s;
            m++; v[m] = t;
            pv.push_back({s, t});
        }
    }
    sort(pv.begin(), pv.end(), cmp);
    if (k == 1 || m == 2) {
        sort(v.begin() + 1, v.begin() + m + 1);
        int bridge = v[(m + 1) / 2];
        for (int i = 1; i <= m; i += 2) {
            ans += abs(bridge - v[i]) + abs(bridge - v[i + 1]) + 1;
        }
        cout << ans + sameside << "\n";
    } else {
        int mn = 1e18;
        for (int i = 2; i <= (m / 2); i++) {
            ans = 0;
            vector<int> A, B;
            for (int j = 1; j <= i - 1; j++) {
                A.push_back(pv[j].first);
                A.push_back(pv[j].second);
            }
            for (int j = i; j <= (m / 2); j++) {
                B.push_back(pv[j].first);
                B.push_back(pv[j].second);
            }
            sort(A.begin(), A.end());
            sort(B.begin(), B.end());
            int bridge1 = A[A.size() / 2];
            int bridge2 = B[B.size() / 2];
            for (int j = 1; j <= i - 1; j++) {
                ans += abs(bridge1 - pv[j].first) + abs(bridge1 - pv[j].second) + 1;
            }
            for (int j = i; j <= (m / 2); j++) {
                ans += abs(bridge2 - pv[j].first) + abs(bridge2 - pv[j].second) + 1;
            }
            mn = min(mn, ans);
        }
        if (m == 0) mn = 0;
        cout << mn + sameside << "\n";
    }
    return 0;
}

/*
2 7
B 1 A 0
A 0 B 0
B 1 B 1
B 1 A 1
B 0 A 1
B 1 A 0
B 0 A 1
*/

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