Submission #1028629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028629		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2098 ms	16832 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);
		}
	}
	n=v.size();
	set<int> se;
	for (int i=0;i<n;i++)
		se.insert(v[i]),se.insert(v1[i]);
	vector<int> pos;
	int ans=n*1e9;
	for (int i:se)
		pos.push_back(i);
	if (k==1)
	{
		sort(v.begin(),v.end());
		sort(v1.begin(),v1.end());
		for (int i=0;i<n;i++)
			pre[i+1]=pre[i]+v[i],pre1[i+1]=pre1[i]+v1[i];
		for (int i=0;i<pos.size();i++)
			ans=min(ans,get(pos[i],v)+get1(pos[i],v1));
	}
	else
	{
		for (int i=0;i<pos.size();i++)
		{
			for (int j=i+1;j<pos.size();j++)
			{
				int val=0;
				for (int a=0;a<n;a++)
					val+=min(abs(v[a]-pos[i])+abs(v1[a]-pos[i]),abs(v[a]-pos[j])+abs(v1[a]-pos[j]));
				ans=min(ans,val);
			}
		}
	}
	cout<<ans+su+n<<endl;
	
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:57:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int i=0;i<pos.size();i++)
      |                ~^~~~~~~~~~~
bridge.cpp:62:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i=0;i<pos.size();i++)
      |                ~^~~~~~~~~~~
bridge.cpp:64:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for (int j=i+1;j<pos.size();j++)
      |                   ~^~~~~~~~~~~

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