Submission #566634

#	Time	Username	Problem	Language	Result	Execution time	Memory
566634		ac2hu	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	0 ms	212 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;
    vector<int> s;
    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{
            s.push_back(a);
            s.push_back(b);
            s.push_back(a - 1);
            s.push_back(b - 1);
            same_part++;
            if(a > b)swap(a, b);
            loc.emplace_back(a, b);
        }
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    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;
    for(auto i : s){
        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());
                sump2 += it.first + it.second;
                sump3 -= abs(it.first - it.second);
                inp2++;
            }
            else break;
        }
        deb(aset, bset);
        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";
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:67:13: warning: unused variable 'p1' [-Wunused-variable]
   67 |         int p1 = sump1 - 2*i*aset.size();
      |             ^~
bridge.cpp:68:13: warning: unused variable 'p2' [-Wunused-variable]
   68 |         int p2 = inp2*2*i - sump2;
      |             ^~

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