제출 #1164521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164521		catsarecool5530	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	29 ms	4540 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n";
#define all(x) x.begin(), x.end()
const ll MOD = 1e9+7;
#define int long long

struct Person {
    ll start, end;
    bool operator<(const Person& other) const {
        return start + end < other.start + other.end;
    }
};

struct House {
    ll location;
    bool isStart;
    bool operator<(const House& other) const {
        return location < other.location;
    }
};

void solve2(int k, int n) {
    vector<Person> people;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        char a, b; int s, e;
        cin >> a >> s >> b >> e;
        if (a == b) {
            sum += abs(e-s);
        } else {
            if (s > e) {
                swap(s, e);
            }
            people.push_back({s, e});
            sum++;
        }
    }
    if (people.size() <= 2) {
        cout << sum << endl;
        return;
    }
    sort(all(people));
    ll minLoss = 0;
    multiset<int> lower;
    multiset<int> upper;
    vector<int> pref(people.size());
    ll pos = 0;
    ll loss = 0;

    for (int i = 0; i < people.size(); i++) {
        ll left = lower.size();
        ll right = upper.size();
        upper.insert(people[i].start);
        upper.insert(people[i].end);
        while (lower.size() < upper.size()) {
            lower.insert(*upper.begin());
            upper.erase(upper.begin());
        }
        assert(lower.size() > 0);
        ll newPos = *lower.rbegin();
        if (i > 0) {
            if (newPos > pos) {
                loss -= left * (newPos - pos);
                loss += right * (newPos - pos);
            } else {
                loss -= lower.size() * (newPos - pos);
                loss += upper.size() * (newPos - pos);
            }
        }
        loss += abs(newPos - people[i].start) + abs(newPos - people[i].end);
        pos = newPos;
        pref[i] = loss;
    }
    lower.clear();
    upper.clear();
    pos = 0;
    loss = 0;
    vector<int> suff(people.size());

    for (int i = people.size()-1; i >= 0; i--) {
        ll left = lower.size();
        ll right = upper.size();
        upper.insert(people[i].start);
        upper.insert(people[i].end);
        while (lower.size() < upper.size()) {
            lower.insert(*upper.begin());
            upper.erase(upper.begin());
        }
        assert(lower.size() > 0);
        ll newPos = *lower.rbegin();
        if (i < people.size()-1) {
            loss -= left * (newPos - pos);
            loss += right * (newPos - pos);
        }
        loss += abs(newPos - people[i].start) + abs(newPos - people[i].end);
        pos = newPos;
        suff[i] = loss;
    }
    minLoss = min(pref.back(), suff[0]);
    for (int i = 0; i < people.size()-1; i++) {
        minLoss = min(minLoss, pref[i] + suff[i+1]);
    }
    cout << sum + minLoss << endl;
}

void solve() {
    int k, n; cin >> k >> n;
    if (k == 2) {
        solve2(k, n);
        return;
    }
    vector<House> houses;
    ll sum = 0;
    ll initLoss = 0;
    int nonTriv = 0;
    for (int i = 0; i < n; i++) {
        char a; int s; char b; int e;
        cin >> a >> s >> b >> e;
        if (a == b) {
            sum += abs(e-s);
        } else {
            nonTriv++;
            if (s > e) {
                swap(s, e);
            }
            sum += abs(e-s);
            sum++;
            initLoss += s;
            houses.push_back({s, true});
            houses.push_back({e, false});
        }
    }

    sort(all(houses));
    ll minLoss = initLoss;
    ll curLoss = initLoss;
    int left = 0;
    int right = nonTriv;
    for (int i = 0; i < houses.size(); i++) {
        if (i > 0) {
            curLoss -= right * (houses[i].location - houses[i-1].location);
            curLoss += left * (houses[i].location - houses[i-1].location);
        } else {
            curLoss -= right * houses[i].location;
        }
        if (houses[i].isStart) {
            right--;
        } else {
            left++;
        }
        
        minLoss = min(minLoss, curLoss);
    }
    cout << sum + minLoss*2 << endl;

}
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    //freopen("example.in", "r", stdin);
    // freopen("hayfeast.out", "w", stdout);
    int t = 1; // cin >> t;
    while (t--) {
        solve();
    }
}

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