Submission #114141

#	Time	Username	Problem	Language	Result	Execution time	Memory
114141		fedoseevtimofey	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	348 ms	25572 KiB

bridge

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;
typedef long double ld;

struct triple {
    int a, b, c;
    bool operator <(const triple &other) const {
        return a < other.a;
    }
};

struct median {
    multiset <int> a, b;
    ll sa, sb;
    void push(int x) {
        if (b.empty() || x >= *b.begin()) {
            b.insert(x);
            sb += x;
        }
        else {
            a.insert(x);
            sa += x;
        }
        while (a.size() > b.size()) {
            int c = *a.rbegin();
            sa -= c;
            sb += c;
            a.erase(--a.end());
            b.insert(c);
        }
        while (b.size() > a.size() + 1) {
            int c = *b.begin();
            sb -= c;
            sa += c;
            b.erase(b.begin());
            a.insert(c);
        }
    }
    ll get() {
        int m = *b.begin();
        return (ll)m * a.size() - sa + sb - (ll)m * b.size();
    }

    median() {
        sa = sb = 0;
    }

};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int k, n;
    cin >> k >> n;
    if (k == 1) {
        ll res = 0;
        vector <int> a;
        for (int i = 0; i < n; ++i) {
            char p, q;
            int x, y;
            cin >> p >> x >> q >> y;
            if (p != q) {
                ++res;
                a.push_back(x);
                a.push_back(y);
            }
            else res += abs(x - y);
        }
        sort(a.begin(), a.end());
        int x = a[(int)a.size() / 2];
        for (auto y : a) res += abs(x - y);
        cout << res << '\n';
    }
    else {
        ll res = 0;
        vector <triple> a;
        for (int i = 0; i < n; ++i) {
            char p, q;
            int x, y;
            cin >> p >> x >> q >> y;
            if (p != q) {
                ++res;
                a.push_back({x + y, x, y});
            }
            else res += abs(x - y);
        }
        sort(a.begin(), a.end());
        int m = a.size();
        vector <ll> f(m + 1), s(m + 1);
        median P;
        for (int i = 0; i < m; ++i) {
            P.push(a[i].b);
            P.push(a[i].c);
            f[i + 1] = P.get();
        }
        median S;
        for (int i = m - 1; i >= 0; --i) {
            S.push(a[i].b);
            S.push(a[i].c);
            s[i] = S.get();
        }
        ll ans = 1e18;
        for (int i = 0; i < m + 1; ++i) ans = min(ans, res + f[i] + s[i]);
        cout << ans << '\n';
    }
}

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