Submission #905828

#	Time	Username	Problem	Language	Result	Execution time	Memory
905828		Faisal_Saqib	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2093 ms	4520 KiB

bridge

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
long long BFG(vector<int>& neq)
{
	int s=0;
	int e=neq.size();
	if(s==e)
		return 0;
	long long final=1e18;
	long long sum=0,ot=0;
	for(int j=s;j<e;j++)
		sum+=neq[j];
	for(int i=s;i<e;i++)
	{
		sum-=neq[i];
		ot+=neq[i];
		long long bf=i+1-s;
		long long af=e-i-1;
		final=min(final,(bf*((long long)(neq[i])))-ot + (sum-(af*((long long)neq[i]))));
	}
	return final;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k,n;
	cin>>k>>n;
	long long total=0;
	vector<pair<int,int>> vlp;
	vector<int> neq;
	for(int j=0;j<n;j++)
	{
		char a,c;
		int b,d;
		cin>>a>>b>>c>>d;
		if(a!=c)
		{
			neq.push_back(b);
			neq.push_back(d);
			vlp.push_back({b,d});
			total+=1;
		}
		else
		{
			total+=abs(b-d);
		}
	}
	sort(begin(neq),end(neq));
	if(k==1)
	{		
		cout<<total+BFG(neq)<<'\n';
	}
	else
	{
		if(vlp.size()==0)
		{
			cout<<total<<'\n';
			return 0;
		}
		// Full Brute force
		long long pl=1e18;
		for(int i=0;i<neq.size();i++)
		{
			for(int j=i+1;j<neq.size();j++)
			{
				long long cur=0;
				for(int k=0;k<vlp.size();k++)
				{
					cur+=min(abs(vlp[k].first-neq[i])+abs(vlp[k].second-neq[i]),abs(vlp[k].first-neq[j])+abs(vlp[k].second-neq[j]));
				}
				pl=min(pl,cur);
			}
		}
		// Did not work
		// long long pl=1e18;
		// for(int j=0;j<vlp.size();j++)
		// {
		// 	vector<int> fpp,spp;
		// 	for(int k=0;k<j;k++)
		// 	{
		// 		fpp.push_back(vlp[k].first);
		// 		fpp.push_back(vlp[k].second);
		// 	}
		// 	for(int k=j;k<vlp.size();k++)
		// 	{
		// 		spp.push_back(vlp[k].first);
		// 		spp.push_back(vlp[k].second);
		// 	}
		// 	sort(begin(fpp),end(fpp));
		// 	sort(begin(spp),end(spp));
		// 	pl=min(pl,BFG(fpp)+BFG(spp));
		// 	// if((BFG(0,j)+BFG(j+1,neq.size()))==5)
		// 	// {
		// 	// 	cout<<"For "<<j<<endl;
		// 	// }
		// }
		cout<<total+pl<<'\n';
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i=0;i<neq.size();i++)
      |               ~^~~~~~~~~~~
bridge.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int j=i+1;j<neq.size();j++)
      |                  ~^~~~~~~~~~~
bridge.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int k=0;k<vlp.size();k++)
      |                 ~^~~~~~~~~~~

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