제출 #1164093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164093		catsarecool5530	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	328 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


void solve() {
    int k, n; cin >> k >> n;
    if (k == 2) {
        cout << -1 << endl;
        return;
    }
    vector<int> start;
    vector<int> end;
    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;
            start.push_back(s);
            end.push_back(e);
        }
    }

    sort(all(start));
    sort(all(end));
    ll minLoss = initLoss;
    ll curLoss = initLoss;
    int left = 0;
    int right = nonTriv;
    int sIndex = 0;
    int eIndex = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            curLoss -= right;
        }
        while (sIndex < start.size() && start[sIndex] <= i) {
            right--;
            sIndex++;
        }
        while (eIndex < end.size() && end[eIndex] < i) {
            left++;
            eIndex++;
        }
        curLoss += 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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37