# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
404657 | sad | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int k,n;ll re=0;
map<ll,int>st,en;
ll no=0,fin=0;
vector<int>v;
int main()
{
cin>>k>>n;ll w=0;
for(int i=0;i<n;i++)
{
char a,b;
int x,y;
cin>>a>>x>>b>>y;
re+=abs(x-y);
if(a==b)continue;
re-=(abs(x-y));
re++;
if(x>y)swap(x,y);
v.pb(x);v.pb(y);
st[x]++;
st[y];no++;
en[y]++;w+=x;
}
ll mn=1e17;
ll last=0;
sort(v.begin(),v.end());
ll r=0;
for(int j=0;j<v.size();j++)
{
w+=fin*(it.fi-last);
w-=no*(it.fi-last);
fin+=en[it.fi];
no-=st[it.fi];
mn=min(mn,w);last=it.fi;
}
if(v.size()==0)mn=0;
re+=mn;
cout<<re;
}