Submission #1020992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020992		Thunnus	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	348 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

vector<pii> opp;
multiset<int> up, low;
int sup = 0, slow = 0;

inline void ins(int val, int len){
	if(low.empty()){
		low.insert(val);
		slow += val;
	}
    else if(val > *low.rbegin()){
        up.insert(val);
        sup += val;
        if(sz(up) > len / 2){
            sup -= *up.begin();
            slow += *up.begin();
            low.insert(*up.begin());
            up.erase(up.begin()); 
        }
    }
    else{
        low.insert(val);
        slow += val;
        if(sz(low) > (len + 1) / 2){
            sup += *low.rbegin();
            slow -= *low.rbegin();
            up.insert(*low.rbegin());
            low.erase(low.find(*low.rbegin()));
        }
    }
}

inline void er(int val){
    auto pos = up.find(val);
    if(pos != up.end()){
        sup -= val;
        up.erase(pos);
    }
    else{
        slow -= val;
        low.erase(low.find(val));
    }
    if(low.empty()){
        slow += *up.begin();
        sup -= *up.begin();
        low.insert(*up.begin());
        up.erase(up.begin());
    }
}

inline int cost(){
    return (*low.rbegin() * sz(low) - slow) + (sup - *low.rbegin() * sz(up));
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int k, n, h, o, ans, plus = 0;
    char home, office;
    cin >> k >> n;
    vector<pii> opp;
    for(int i = 0; i < n; i++){
        cin >> home >> h >> office >> o;
        if(home == office){
            plus += abs(o - h);
        }
        else{
            opp.emplace_back(h, o);
            plus++;
        }
    }
    
    n = sz(opp);
    vi pref_ans(n);
    sort(opp.begin(), opp.end(), [](const pii &a, const pii &b) {return a.fi + a.se > b.fi + b.se;} );

    for(int i = 0; i < n; i++){
        ins(opp[i].fi, i * 2);
        ins(opp[i].se, i * 2 + 1);
        pref_ans[i] = cost();
    }
    if(k == 1)
        ans = pref_ans.back();
    else{
        ans = pref_ans.back();
        for(int i = 0; i < n - 1; i++){
            er(opp[i].fi);
            er(opp[i].se);
            ans = min(ans, pref_ans[i] + cost());
        }
    }
    cout << ans + plus;
    return 0;
}

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