Submission #112164

#	Time	Username	Problem	Language	Result	Execution time	Memory
112164		Runtime_error_	Palembang Bridges (APIO15_bridge)	C++14	9 / 100	2060 ms	512 KiB

bridge

//APIO 2015 Palembang Bridges
//3-3 subtasks solution 8 points
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll k,n,ans,cnt,sum;
vector<pair<ll,ll> > v;
vector<ll> all;

ll go(ll pos1,ll pos2){
    ll ret=0;
    for(auto o:v)
        ret+=min(abs(o.first-pos1)+abs(o.second-pos1),abs(o.first-pos2)+abs(o.second-pos2));
    return ret;
}

int main(){

    cin>>k>>n;
    for(ll i=1;i<=n;i++){
        char x,y;
        ll a,b;
        cin>>x>>a>>y>>b;
        if(x==y)
            ans+=abs(a-b);
        else
            v.push_back(  x=='A'?make_pair(a,b):make_pair(b,a) ),sum+=a+b,cnt+=2,all.push_back(a),all.push_back(b);
    }
    if(cnt){
        ans+=cnt/2;
        ll temp=1e18+9;
        for(auto o:all)
            for(auto u:all)
                temp=min(temp,go(o,u));
        ans+=temp;
    }
    //cout<<sum<<" "<<go(sum)<<" "<<go(sum+1)<<" "<<go(sum-1)<<endl;
    cout<<ans<<endl;
}

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