Submission #882460

#	Time	Username	Problem	Language	Result	Execution time	Memory
882460		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	32 ms	2600 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 > v;
    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{
            v.push_back(p1);
            v.push_back(p2);
        }
    }
    if(v.size()){
        sort(v.begin() , v.end());
        vector < int > cand;
        cand.push_back(v[(v.size()-1)/2]);
        cand.push_back(v[v.size()/2]);
        for(auto itr : cand){
            int locans = v.size()/2;
            for(auto itr1 : v){
                locans += abs(itr1 - itr);
            }
            //cout << itr << " : " << locans + ek << endl;
            ans = min(ans , locans);
        }
    }
    else ans = 0;
    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: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37