Submission #1210269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210269		anfi	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	205 ms	12160 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e18;

bool cmp(pair<int,int> a, pair<int,int> b){
    return a.fi+a.se < b.fi+b.se;
}
int lsum = 0, rsum =0;
multiset<int> h,d;

void tambah(int n){
    if(d.empty() || *(--d.end()) >= n) d.insert(n), lsum+=n;
    else h.insert(n), rsum+= n;
    while(h.size() >= d.size()) rsum -= *h.begin(), lsum += *h.begin(), d.insert(*h.begin()), h.erase(h.begin());
    while(h.size()+1 < d.size()) lsum -= *(--d.end()), rsum += *(--d.end()), h.insert(*(--d.end())), d.erase((--d.end()));
}

signed main(){
    int k,nn,ans = 0; cin >> k >> nn;
    vector<pair<int,int>> p;
    for(int i = 0;i < nn; i++){
        int u,v;
        char a,b;
        cin >> a >> u >> b >> v;
        if(a == b) ans += abs(u-v);
        else ++ans, p.push_back({u, v});
    }
    int l = p.size();
    sort(p.begin(), p.end(), cmp);
    vector<int> n(l);
    if(l == 0){
        cout << ans;
        exit(0);
    }
    for(int i = 0; i < l; i++){
        tambah(p[i].fi), tambah(p[i].se), n[i] += rsum-lsum;
    }
    if(k == 1){
        cout << ans+n[l-1];
        exit(0);
    }
    h.clear(); d.clear();
    rsum = lsum = 0;
    int mn = n[l-1];
    for(int i = l-1; i >= 1; i--){
        tambah(p[i].fi), tambah(p[i].se), mn = min(mn, n[i-1]+rsum-lsum);
    }
    cout << ans+mn;
}

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