Submission #91555

#	Time	Username	Problem	Language	Result	Execution time	Memory
91555		Bodo171	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	47 ms	21360 KiB

bridge

#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
using namespace std;
const int nmax=100005;
pair<int,int> v[nmax],a[2*nmax];
long long act,neinc,term,sum_neinc,sum_term,ans,fx;
char wh1,wh2;
int n,i,j,k,p1,p2,cate;
long long abss(long long x)
{
    if(x<0) return  -x;
    return x;
}
void solve_1()
{
    for(i=1;i<=cate;i++)
    {
        a[2*i-1]={v[i].first,-1};
        a[2*i]={v[i].second,1};
        sum_neinc+=1LL*v[i].first;
    }
    neinc=cate;
    sort(a+1,a+2*cate+1);ans=LLONG_MAX;
    if(!cate) ans=0;
    for(i=1;i<=2*cate;i++)
    {
        if(a[i].second==-1)
            neinc--,sum_neinc-=1LL*a[i].first;
        else term++,sum_term+=1LL*a[i].first;
        act=a[i].first;
        ans=min(ans,2LL*(sum_neinc-neinc*act+term*act-sum_term));
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>k>>n;
    for(i=1;i<=n;i++)
    {
        cin>>wh1>>p1>>wh2>>p2;
        fx+=(1LL*abss(p2-p1));
        if(wh1!=wh2)
        {
            fx++;
            if(p1>p2) swap(p1,p2);
            v[++cate]={p1,p2};
        }
    }
    if(k==1)
        solve_1();
    cout<<fx+ans;
    return 0;
}

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