Submission #882447

#	Time	Username	Problem	Language	Result	Execution time	Memory
882447		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	604 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int k , n , ans = 1e18 + 7 , ek = 0;
    cin >> k >> n;
    vector < int > A,B;
    vector < pair < int , int > > consider;
    for(int i = 0;i<n;i++){
        char c1,c2;
        int p1,p2;
        cin >> c1 >> p1;
        cin >> c2 >> p2;
        if(c1 == c2){
            ek += abs(p1-p2);
        }
        else{
            if(c1 == 'A')A.push_back(p1);
            else B.push_back(p1);

            if(c2 == 'A')A.push_back(p2);
            else B.push_back(p2);

            consider.push_back({p1,p2});
        }
    }
    sort(A.begin() , A.end());
    sort(B.begin() , B.end());
    //cout << "A : ";for(auto itr : A)cout << itr << " ";cout << endl;
    //cout << "B : ";for(auto itr : B)cout << itr << " ";cout << endl;
    pair < int , int > r1 , r2;
    r1 = {A[((int)A.size()-1)/2] , A[(int)A.size()/2]};
    r2 = {B[((int)B.size()-1)/2] , B[(int)B.size()/2]};
    //cout << "r1 : " << r1.first << " " << r1.second << endl;
    //cout << "r2 : " << r2.first << " " << r2.second << endl;
    vector < int > cand;
    if(r1.first > r2.first)swap(r1,r2);
    if(r1.second > r2.first)cand.push_back(r1.second-1);
    else {
        cand.push_back((r1.second + r2.first) / 2+1);
        cand.push_back((r1.second + r2.first) / 2);
        cand.push_back((r1.second + r2.first) / 2-1);
    }
    //cout << "cand : ";for(auto itr : cand)cout << itr << " ";cout << endl;
    for(auto itr : cand){
        int locans = 0;
        for(auto itr1 : consider){
            locans += abs(itr1.first - itr) + abs(itr1.second - itr) + 1;
        }
        //cout << itr << " : " << locans + ek << endl;
        ans = min(ans , locans);
    }
    cout << ans + ek << endl;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int testcase = 1;//cin >> testcase;
    while(testcase--)solve();
}

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