Submission #1378856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1378856		Godgift42	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	344 KiB

bridge

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

const ll inf=1000000000000000000;

int main(){
    int n,k;
    cin >> k >> n;
    if(k==1){
        ll ans=0;
        vector<pair<ll,ll>> a;
        vector<ll> ra;
        for(int i=0;i<n;i++){
            char p,q;
            int b,s;
            cin >> p >> b >> q >> s;
            
            if(p!=q){
                if(b>s)swap(b,s);
                a.push_back({b,s});
                ra.push_back(s);
            }
            else ans+=abs(b-s);
        }
        sort(a.begin(),a.end());
        sort(ra.begin(),ra.end());
        int sz=a.size();
        vector<ll> prm(sz+1,0);
        ll de=a[0].first;
        for(int i=1;i<=sz;i++){
            prm[i]=prm[i-1]+ra[i-1];
            de+=a[i-1].first;
        }
        ll cs=inf;
        ll ar=0;
        for(int i=0;i<sz;i++){
            ar+=a[i].first;
            de-=a[i].first;
            ll cur=sz+(i+1)*a[i].first-ar+de-(sz-i-1)*a[i].first;
            auto it=upper_bound(ra.begin(),ra.end(),a[i].first)-ra.begin();
            cur+=a[i].first*it-prm[it]+prm[sz]-prm[it]-a[i].first*(sz-it);
            cs=min(cs,cur);
        }
        cout << ans+cs << "\n";
    }   
}

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