Submission #521181

#	Time	Username	Problem	Language	Result	Execution time	Memory
521181		Sharky	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	46 ms	4168 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
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() + 1, pv.begin() + pv.size());
    if (k == 1) {
        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 bridge1, bridge2;
        int totans = 1e18; 
        for (int i = 1; i <= m; i++) {
            ans = 0;
            bridge1 = v[i];
            int idx = m / 2;
            vector<int> tmp; 
            for (int j = 1; j <= (m / 2); j++) {
                if (pv[j].first > bridge1) {
                    idx = j; break;
                }
            }
            for (int j = idx; j <= (m / 2); j++) {
                tmp.push_back(pv[j].first);
                tmp.push_back(pv[j].second);
            }
            sort(tmp.begin(), tmp.end());
            bridge2 = tmp[(tmp.size()) / 2];
            //. cout << bridge1 << " " << bridge2 << "\n";
            for (int j = 1; j <= (m / 2); j++) {
                int fb, sb;
                fb = abs(bridge1 - pv[j].first) + abs(bridge1 - pv[j].second) + 1;
                sb = abs(bridge2 - pv[j].first) + abs(bridge2 - pv[j].second) + 1;
                ans += min(fb, sb);
            }
            totans = min(totans, ans);
        }
        // cout << bridge1 << " " << bridge2 << "\n";
        
        cout << totans + sameside << "\n";
    }
    return 0;
}

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