제출 #487337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487337		leaked	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	332 KiB

bridge

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e18;
signed main(){
    fast_iati;

    int k,n;
    cin>>k>>n;
    vec<int>l,r;
    ll ans=0;
    vec<int>kek;
    vec<int>pref;
    for(int i=0;i<n;i++){
        char f,s;
        int x,y;
        cin>>f>>x>>s>>y;
        if(f==s) ans+=abs(x-y);
        else{
            if(x>y) swap(x,y);
            l.pb(x);r.pb(y);
        }
    }
    n=sz(l);
    for(int i=0;i<n;i++){
        kek.pb(l[i]);kek.pb(r[i]);
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    pref.assign(sz(kek)+1,0);
    for(int i=0;i<n;i++){
        l[i]=lower_bound(all(kek),l[i])-kek.begin();
        r[i]=lower_bound(all(kek),r[i])-kek.begin();
        pref[l[i]]++,pref[r[i]+1]--;
    }
    for(int i=1;i<=sz(kek);i++){
        pref[i]+=pref[i-1];
    }
    int j=*max_element(all(pref));
    if(k==1){
        ll mn=inf;
        for(int i=0;i<sz(kek);i++){
            int x=kek[i];
            if(pref[i]<j) continue;
            ll me=0;
            for(int k=0;k<n;k++){
                me+=abs(x-kek[l[k]]);
                me+=abs(x-kek[r[k]])+1;
            }
//            cout<<"ALO "<<x<<' '<<me<<endl;
            umin(mn,me);
        }
        if(!sz(kek)){
            cout<<ans;
            return 0;
        }
//        cout<<ans<<endl;
        cout<<ans+mn;
    }
    else{
    cout<<22;}
    return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

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