Submission #530297

#	Time	Username	Problem	Language	Result	Execution time	Memory
530297		Nghes	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	239 ms	15200 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<=(int)(b);++i)
#define FORB(i,a,b) for(int i=(a);i>=(int)(b);--i)
#define E '\n'
#define name "main"
#define X first
#define Y second
#define int ll
#define ii pair<int,int>

const ll oo = 1e18+19;
const int N = 1e5;
multiset<int> low;
multiset<int> up;
int numBrigde, numPeople;
int pre[N+13];
int suf[N+13];
int sameside;
int sumLow;
int sumUp;
vector<ii> people;
bool minimize(ll &x, ll y){
    return x > y ? x = y,1 : 0;
}
void ins(int x){
    if (low.size() && *low.rbegin() < x) up.insert(x),sumUp += x;
    else low.insert(x), sumLow += x;
    while(up.size() > low.size()){
        sumLow += *up.begin();
        sumUp -= *up.begin();
        low.insert(*up.begin());
        up.erase(up.find(*up.begin()));
    }
    while(low.size() - 1 > up.size()){
        sumLow -= *low.rbegin();
        sumUp += *low.rbegin();
        up.insert(*low.rbegin());
        low.erase(low.find(*low.rbegin()));
    }
}
int getMed(){
    return *low.rbegin();
}
void prepare(){
    low.clear(); up.clear();
    sumUp = sumLow = 0;
    FOR(i,0,people.size()-1){
        ins(people[i].X);
        ins(people[i].Y);

        pre[i] = (getMed()*low.size() - sumLow) + (sumUp - getMed()*up.size());
    }
    low.clear(); up.clear();
    sumUp = sumLow = 0;
    FORB(i,people.size()-1,0){
        ins(people[i].X);
        ins(people[i].Y);
        suf[i] = (getMed()*low.size() - sumLow) + (sumUp - getMed()*up.size());
    }
}
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout .tie(0);
//    freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
    cin >> numBrigde >> numPeople;
    FOR(i,1,numPeople){
        char Ax,By;
        int x,y;
        cin >> Ax >> x >> By >> y;
        if (Ax == By)
            sameside += abs(x - y);
        else
            people.push_back(ii(x,y));
    }
    sort(people.begin(),people.end(),[&](ii A,ii B){
        return (A.X + A.Y) < (B.X + B.Y);
    });
    prepare();

    ll res = oo;

    if (numBrigde == 1) res = pre[people.size()-1];
    else {
        FOR(i,1,people.size()-1){
            minimize(res,suf[i] + pre[i-1]);
        }
    }
    cout << res + sameside + people.size();

    return 0;
}

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