제출 #1058943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058943		sammyuri	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2023 ms	15972 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll base_cost;
int n, k;
vector<pair<int, int>> paths;

ll check(int firstbridge, bool skip = false) {
    // all paths that start on the left of firstbridge must use it
    // so we only care about paths entirely to the right
    // for each of those paths, keep track of when cost stops decreasing,
    // and when it starts increasing
    ll overhead = 0;
    ll diff = 0;
    map<int, ll> dx;
    for (int i = 0; i < n; i ++) {
        if (paths[i].second < firstbridge || paths[i].first > firstbridge)
            overhead += (ll)abs(firstbridge - paths[i].first) + abs(firstbridge - paths[i].second);
        else
            overhead += (ll)abs(paths[i].second - paths[i].first);
        if (skip || paths[i].first > firstbridge) {
            diff -= 2;
            dx[paths[i].first] += 2;
            dx[paths[i].second] += 2;
            if (!skip) {
                ll min_eq = paths[i].second + (paths[i].first - firstbridge);
                if (min_eq <= 1000000000)
                    dx[min_eq] -= 2;
            }
        }
    }
    int last = firstbridge;
    ll best = overhead;
    for (auto a : dx) {
        int curdist = a.first, dd = a.second;
        overhead += (ll)(curdist - last) * diff;
        diff += dd;
        best = min(best, overhead);
        // cout << a.first << " " << overhead + base_cost << endl;
        last = curdist;
    }
    return best;
}


int main() {
    cin >> k >> n;
    base_cost = 0;
    for (int i = 0; i < n; i ++) {
        char a, b;
        int x, y;
        cin >> a >> x >> b >> y;
        if (a == b) {
            base_cost += abs(y - x);
        } else {
            base_cost ++;
            paths.push_back({min(x, y), max(x, y)});
        }
    }
    n = paths.size();
    sort(paths.begin(), paths.end());
    if (n == 0) {
        cout << base_cost << endl; return 0;
    }
    if (k == 1) {
        cout << check(0, true) + base_cost << endl; return 0;
    }
    // brute force
    ll best = 1e18;
    for (int i = 0; i < n; i ++) {
        best = min(best, check(paths[i].first, false));
        best = min(best, check(paths[i].second, false));
    }
    cout << best + base_cost << endl; return 0;
}

/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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