Submission #582486

#	Time	Username	Problem	Language	Result	Execution time	Memory
582486		gg123_pe	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	129 ms	4328 KiB

bridge

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 2005; 
const ll inf = 1e9;


int k, n; 
ll ans, mini; 
vector <ii> v; 

ll get(ll i){   
    ll res = 0; 
    for(auto p: v){
        ll a = p.first, b = p.second; 
        if(i < a) res += a + b + 1 - 2*i; 
        else if(b < i) res += 2*i + 1 - a - b; 
        else res += b - a + 1; 
    }
    return res; 
}
int main(){
    cin >> k >> n; 

    f(i,1,n+1){
        char x, y; 
        ll a, b; 

        cin >> x >> a >> y >> b; 
        
        if(x == y){
            ans += abs(b-a);
        }
        else{
            v.push_back({min(a,b), max(a, b)}); 
        }
    }

    ll l = 0, r = inf; 

    while(l < r){
        ll m = (l+r)>>1; 
        if(get(m) < get(m+1)) r = m; 
        else l = m+1; 
    }
    cout << ans + get(l) << "\n"; 
    return 0;
}

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