제출 #1028618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028618		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	8 / 100	47 ms	7112 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 1e5 + 1;

int pre[M]={},pre1[M]={},n;

int get(int a,vector<int> &v)
{
	int x=upper_bound(v.begin(),v.end(),a)-v.begin();
	return abs(a*x-pre[x]+pre[n]-pre[x]-(n-x)*a);
}

int get1(int a,vector<int> &v)
{
	int x=upper_bound(v.begin(),v.end(),a)-v.begin();
	return abs(a*x-pre1[x]+pre1[n]-pre1[x]-(n-x)*a);
}

signed main()
{
	int k,su=0;
	cin>>k>>n;
	vector<int> v,v1;
	for (int i=0;i<n;i++)
	{
		char c,c1;
		int x,y;
		cin>>c>>x>>c1>>y;
		if (c==c1)
			su+=abs(y-x);
		else
		{
			if (c=='B')
				swap(x,y);
			v.push_back(x);
			v1.push_back(y);
		}
	}
	sort(v.begin(),v.end());
	sort(v1.begin(),v1.end());
	n=v.size();
	set<int> se;
	for (int i=0;i<n;i++)
		pre[i+1]=pre[i]+v[i],pre1[i+1]=pre1[i]+v1[i],se.insert(v[i]),se.insert(v1[i]);
	vector<int> pos;
	int ans=n*1e9;
	for (int i:se)
		pos.push_back(i);
	for (int i=0;i<n*2;i++)
		ans=min(ans,get(pos[i],v)+get1(pos[i],v1));
	cout<<ans+su+n<<endl;
	
	return 0;
}

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