제출 #1057091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057091		nickshen	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	436 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ss second
#define ff first
typedef vector<pair<int, int>> vpi;
typedef vector<int> vi;
void solve() {
    int k, n;
    cin >> k >> n;
    int ans = 0;
    map<int, int> mp;
    vpi v;
    for (int i = 0; i < n; i++) {
        char a, b;
        int c, d;
        cin >> a >> c >> b >> d;
        if (a == b)
            ans += abs(d - c);
        else {
            if (c > d) swap(c, d);
            mp[c]++;
            mp[d + 1]--;
            v.push_back({c, d});
        }
    }
    vi t;
    int mx = 0, p = 0;
    while (k--) {
        int cur = 0;
        for (auto u : mp) {
            cur += u.ss;
            if (mx <= cur) {
                mx = cur;
                p = u.ff;
            }
        }
        for (auto u : v) {
            if (u.ff <= p && u.ss >= p) {
                mp[u.ff]--;
                mp[u.ss + 1]++;
            }
        }
        t.push_back(p);
        mx = 0;
        p = 0;
    }
    for (auto u : v) {
        int mn = 1e10;
        for (auto j : t) {
            mn = min(mn, abs(j - u.ff) + 1 + abs(j - u.ss));
        }
        ans += mn;
    }
    cout << ans << "\n";
}

/*
Fact 1: add a bridge between office and home and add a bridge at the end of office or home are the same -> just add at the end
Fact 2: if pair a is inside pair b, ignore pair b
Fact 3: ignore pair on the same side
Fact 4: it is optimal to choose a point with maximum pair included
*/

/*
Step:
1. Find the point with maximum number of pair included in each loop
2. erase all pair included in the point
3. Calculate the minimum cost after k point is used

time: O(n*log(n))


*/

signed main() {
    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