Submission #1265853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265853		canhnam357	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	152 ms	12972 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, n;
    cin >> T >> n;
    if (T == 1) {
        long long ans = 0;
        vector<int> a;
        for (int i = 0; i < n; i++) {
            char x, y;
            int c, d;
            cin >> x >> c >> y >> d;
            if (x == y) ans += abs(c - d);
            else a.push_back(c), a.push_back(d), ans++;
        }
        sort(a.begin(), a.end());
        for (int i : a) {
            ans += abs(i - a[a.size() / 2]);
        }
        cout << ans << '\n';
    } 
    else {
        vector<pair<int, int>> a;
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            char x, y;
            int c, d;
            cin >> x >> c >> y >> d;
            if (x == y) ans += abs(c - d);
            else a.emplace_back(c, d), ans++;
        } 
        sort(a.begin(), a.end(), [&](auto i, auto j) {
            return i.first + i.second < j.first + j.second;
        });
        n = a.size();
        vector<long long> pre(n), suf(n);
        {
            long long suml = 0, sumr = 0;
            multiset<int> r;
            multiset<int, greater<int>> l;
            l.insert(INT_MIN);
            r.insert(INT_MAX);
            for (int i = 0; i < n; i++) {
                auto [x, y] = a[i];
                if (x > *l.begin()) r.insert(x), sumr += x;
                else l.insert(x), suml += x;
                if (y > *l.begin()) r.insert(y), sumr += y;
                else l.insert(y), suml += y;
                while (r.size() - 1 > l.size()) {
                    int x = *r.begin();
                    r.erase(r.begin());
                    sumr -= x;
                    suml += x;
                    l.insert(x);
                }
                while (l.size() > r.size()) {
                    int x = *l.begin();
                    l.erase(l.begin());
                    suml -= x;
                    sumr += x;
                    r.insert(x);
                }
                pre[i] = sumr - (r.size() - 1LL) * *r.begin() + (l.size() - 1LL) * *r.begin() - suml;
            }
        }
        {
            long long suml = 0, sumr = 0;
            multiset<int> r;
            multiset<int, greater<int>> l;
            l.insert(INT_MIN);
            r.insert(INT_MAX);
            for (int i = n - 1; i >= 0; i--) {
                auto [x, y] = a[i];
                if (x > *l.begin()) r.insert(x), sumr += x;
                else l.insert(x), suml += x;
                if (y > *l.begin()) r.insert(y), sumr += y;
                else l.insert(y), suml += y;
                while (r.size() - 1 > l.size()) {
                    int x = *r.begin();
                    r.erase(r.begin());
                    sumr -= x;
                    suml += x;
                    l.insert(x);
                }
                while (l.size() > r.size()) {
                    int x = *l.begin();
                    l.erase(l.begin());
                    suml -= x;
                    sumr += x;
                    r.insert(x);
                }
                suf[i] = sumr - (r.size() - 1LL) * *r.begin() + (l.size() - 1LL) * *r.begin() - suml;
            }
        }
        if (n > 0) {
            long long add = min(pre[n - 1], suf[0]);
            for (int i = 1; i < n; i++) {
                add = min(add, pre[i - 1] + suf[i]);
            }
            ans += add;
        }
        cout << ans << '\n';
    }
    return 0;
}

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