Submission #566619

#	Time	Username	Problem	Language	Result	Execution time	Memory
566619		ac2hu	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	340 KiB

bridge

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,k;cin >> k >> n;
    vector<pair<int,int>> loc;
    int same_part = 0;
    for(int i = 0;i<n;i++){
        char c1, c2;
        int a,b;
        cin >> c1 >> a >> c2 >> b;
        if(c1 == c2){
            same_part += abs(a - b);
        }
        else{
            same_part++;
            if(a > b)swap(a, b);
            loc.emplace_back(a, b);
        }
    }
    // deb(loc);
    multiset<pair<int,int>> aset, bset;
    for(auto e : loc)aset.insert(e);
    int ans = 1e18;
    int sump1 = 0;
    int sump2 = 0;
    int sump3 = 0;
    int inp2 = 0;
    for(auto e : aset)sump1 += e.first + e.second;
    set<pair<int,int>> extra;
    for(int i = 0;i<=10;i++){
        while(aset.size() > 0){
            auto it = *aset.begin();
            if(i >= it.first){
                bset.insert({it.second, it.first});
                aset.erase(aset.begin());
                sump1 -= it.first + it.second;
                sump3 += abs(it.first - it.second);
            }
            else
                break;
        }
        while(bset.size() > 0){
            auto it = *bset.begin();
            if(i >= it.first){
                bset.erase(bset.begin());
                extra.insert(it);
                sump2 += it.first + it.second;
                sump3 -= abs(it.first - it.second);
                inp2++;
            }
            else break;
        }
        // deb(aset, bset, extra);
        // int p1 = sump1 - 2*i*aset.size();
        // int p2 = inp2*2*i - sump2;
        // deb(same_part, p1, p2, sump3);
        ans = min(ans, same_part + (sump1 - 2*i*(int)aset.size()) + (inp2*2*i - sump2) + sump3);
    }
    cout << ans << "\n";
}

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