Submission #119427

#	Time	Username	Problem	Language	Result	Execution time	Memory
119427		Charis02	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	384 KiB

bridge

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

ll n,k;
pi ar[N];
ll b,d;
char a,c;
ll ans,cnt;

ll checkbridge(ll x)
{
    ll bridge = x;
    ll res = ans;

    rep(j,0,cnt)
    {
        if(ar[j].first <= bridge && bridge <= ar[j].second)
            continue;
        else if(bridge < ar[j].first)
            res += 2*(ar[j].first - bridge);
        else
            res += 2*(bridge-ar[j].second);
    }

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >>  k >> n;

    rep(i,0,n)
    {
        cin >> a >> b >> c >> d;

        if(d < b)
            swap(b,d);

        ans += d-b;
        if(a != c)
        {
            ar[cnt].first = b;
            ar[cnt].second = d;
            ans++;
            cnt++;
        }
    }

    sort(ar,ar+cnt);
    ll fin = INF;

    rep(i,0,cnt)
    {
        /*cout << ar[i].first << " " << checkbridge(ar[i].first) << endl;
        cout << ar[i].second << " " << checkbridge(ar[i].second) << endl;
        cout << endl;
       */ fin = min(fin,checkbridge(ar[i].first));
        fin = min(fin,checkbridge(ar[i].second));
    }

    cout << fin;

    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