Submission #114120

#	Time	Username	Problem	Language	Result	Execution time	Memory
114120		fedoseevtimofey	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	68 ms	10876 KiB

bridge

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;
typedef long double ld;

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;
    vector <pair <int, int>> a;
    ll res = 0;
    vector <pair <int, int>> e;
    vector <int> c;
    ll cur = 0;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; ++i) {
        char p, q;
        int x, y;
        cin >> p >> x >> q >> y;
        res += abs(x - y);
        if (x > y) swap(x, y);
        if (p != q) {
            e.push_back({x, -1});
            e.push_back({y, 1});
            a.emplace_back(x, y);
            cur += 2 * x;
            ++cnt1;
            ++res;
        }
        c.push_back(x);
        c.push_back(y);
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    sort(e.begin(), e.end());
    assert(k == 1);
    ll ans = cur + res;
    for (int i = 0; i < (int)e.size(); ++i) {
        cur -= 2LL * cnt1 * (e[i].first - (i == 0 ? 0 : e[i - 1].first));
        cur += 2LL * cnt2 * (e[i].first - (i == 0 ? 0 : e[i - 1].first));
        if (e[i].second == -1) --cnt1;
        else ++cnt2;
        ans = min(ans, res + cur);
    }
    cout << ans << '\n';
}

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