Submission #499130

#	Time	Username	Problem	Language	Result	Execution time	Memory
499130		Stickfish	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	108 ms	5324 KiB

bridge

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;
using ll = long long;

const ll INF = 1.77013e15;

const int MAXN = 100003;
pair<ll, ll> sg[MAXN];
ll pref_ans[MAXN];
ll suf_ans[MAXN];

signed main() {
    ll k, n = 0;
    ll n0;
    cin >> k >> n0;
    ll addans = 0;
    for (int i = 0; i < n0; ++i) {
        char c1, c2;
        ll d1, d2;
        cin >> c1 >> d1 >> c2 >> d2;
        if (d1 > d2)
            swap(d1, d2);
        d1 *= 2;
        d2 *= 2;
        if (c1 == c2) {
            addans += d2 - d1;
        } else {
            sg[n] = {(d1 + d2) / 2, (d2 - d1) / 2};
            ++n;
        }
    }
    sort(sg, sg + n);
    if (k == 1) {
        vector<int> event;
        for (int i = 0; i < n; ++i) {
            pair<ll, ll> t = sg[i];
            event.push_back(t.first - t.second);
            event.push_back(t.first + t.second);
        }
        sort(event.begin(), event.end());
        ll x = event[n - 1];
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += abs(x - sg[i].first + sg[i].second);
            ans += abs(x - sg[i].first - sg[i].second);
        }
        cout << (ans + addans) / 2 + n << endl;
    } else {
        return 0;
    }
}

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