Submission #1154560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154560		nrg_studio	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	163 ms	12188 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, k; cin >> k >> n;
    ll add = 0;
    v<pii> people;

    F0R(i,n) {
        char a, b; int c, d; 
        cin >> a >> c >> b >> d;

        if (a==b) {add += abs(d-c);}
        else {
            people.pb({c,d});
        }
    }
    sort(all(people),[&](pii a, pii b) {return a.f+a.s<b.f+b.s;});
    
    //ll ans1 = 0;
    //for (int i : pos) {ans1 += abs(i-pos[(pos.size()-1)/2]);}

    v<ll> cost(people.size()+1,0), cost2(people.size()+1,0);


    F0R(cnt,2) {
        multiset<ll> left, right;
        ll lsum = 0, rsum = 0;
        int c = 0;

        auto doit = [&](int a) {
            c++;
            if (right.size() && a>*right.begin()) {right.insert(a); rsum += a;}
            else {left.insert(a); lsum += a;}

            if (left.size()>(c+1)/2) {
                int d = *left.rbegin();
                lsum -= d; rsum += d;
                right.insert(d);
                left.erase(left.find(d));
            } else if (right.size()>c-(c+1)/2) {
                int d = *right.begin();
                lsum += d; rsum -= d;
                right.erase(right.find(d));
                left.insert(d);
            }
        };

        F0R(i,people.size()) { // split past i
            doit(people[i].f); doit(people[i].s);
            ll med = *left.rbegin();
            cost[i+1] = (med*left.size()-lsum) + (rsum-med*right.size());
            //cout << cost[i+1] << '\n';
        }
        swap(cost,cost2);
        reverse(all(people));
        //break;
    }
    ll ans = cost.back();
    if (k==2) {
        F0R(i,people.size()) {
            chmin(ans,cost[i]+cost2[people.size()-i]);
        }
    }
    cout << ans+add+people.size() << '\n';


    /*
    get rid of p=q first
    make sure start<end

    one bridge
    do median

    two bridges
    sort people by bottom then top
    fix breakpoint for people and calc medians of each



    multiset for smaller elements and multiset for larger elements
    adding new element:
    add to correct multiset and shift elements between them
    store sum for both multisets
    */


}

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