Submission #905861

#	Time	Username	Problem	Language	Result	Execution time	Memory
905861		Faisal_Saqib	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	43 ms	2452 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));
	sort(begin(vlp),end(vlp));
	if(k==1)
	{		
		cout<<total+BFG(neq)<<'\n';
	}
	else
	{
		if(vlp.size()==0)
		{
			cout<<total<<'\n';
			return 0;
		}
		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<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int j=0;j<vlp.size();j++)
      |               ~^~~~~~~~~~~
bridge.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(int k=j;k<vlp.size();k++)
      |                ~^~~~~~~~~~~

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