Submission #689395

#	Time	Username	Problem	Language	Result	Execution time	Memory
689395		thienbao1602	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	468 KiB

bridge

#include    <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
using namespace std;

const ll INF = 1e9 + 1;

int n, K;
ll lSum = 0, rSum = 0, cur = 0;
priority_queue<ll> lStore;
priority_queue<ll, vector<ll>, greater<ll>> rStore;

bool cmp(pair<ll, ll>& x, pair<ll, ll>& y)
{
    return x.fi + x.se < y.fi + y.se;
}

void add(ll x)
{
    ll median = (lStore.empty() ? INF : lStore.top());
    if (x <= median)
    {
        lStore.push(x);
        lSum += x;
    } else
    {
        rStore.push(x);
        rSum += x;
    }

    if (sz(lStore) > 1 + sz(rStore))
    {
        ll tmp = lStore.top();
        lStore.pop();
        rStore.push(tmp);
        lSum -= tmp, rSum += tmp;
    }

    if (sz(lStore) < sz(rStore))
    {
        ll tmp = rStore.top();
        rStore.pop();
        lStore.push(tmp);
        lSum += tmp, rSum -= tmp;
    }
}

void solve()
{
    cin >> K >> n;
    vector<pair<ll, ll>> a;
    for(int i=0; i<n; i++)
    {
        ll x, y;
        char P, Q;
        cin >> P >> x >> Q >> y;
        if (P == Q) cur += abs(x - y);
         else a.push_back({x, y});
    }

    n = a.size(), cur += n;
    sort(a.begin(), a.end(), cmp);

    vector<ll> pref(n, 0);
    for(int i=0; i<n; i++)
    {
        add(a[i].fi);
        add(a[i].se);
        pref[i] = rSum - lSum;
    }


    ll ret = pref[n - 1];
    if (K == 2)
    {
        while(!lStore.empty()) lStore.pop();
        while(!rStore.empty()) rStore.pop();

        lSum = rSum = 0;
        vector<ll> suf(n, 0);
        for(int i=n-1; i>0; i--)
        {
            add(a[i].fi), add(a[i].se);
            ret = min(ret, pref[i - 1] + rSum - lSum);
        }
    }
    cout << ret + cur;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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