Submission #1319701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319701		Faisal_Saqib	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	196 ms	512 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ld long double
main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	bool use[n+2]={0};
	pair<ld,ld> c[n+2];
	pair<ld,ld> og[n+2];
	pair<ld,int> a[n+2],b[n+2];
	for(int i=0;i<n;i++)
	{
		cin>>a[i].first>>b[i].first;
		// if(b[i].first==-1)b[i].first=1e10;
		a[i].second=i;
		b[i].second=i;
		c[i].first=-a[i].first+b[i].first;
		c[i].second=b[i].first;
		og[i].first=a[i].first;
		og[i].second=b[i].first;
		// cout<<"Val ";
		// cout<<og[i].first<<' '<<og[i].second<<' '<<i<<endl;
	}
	cout.precision(4);
	ld ot=0,cst=0;
	sort(a,a+n);
	ld ans=0;
	for(int i=0;i<k;i++)ans+=a[i].first;
	vector<int> allp;
	for(int l=1;l<=k;l++)
	{
		for(int j=0;j<n;j++)
			use[j]=0;
		ld cur=0;
		bool fk=0;
		vector<ld> tpl;
		// cout<<"For "<<l<<endl;
		for(int i=l;i>=1;i--)
		{
			ld mi=1e10;
			int ind=-1;
			for(int j=0;j<n;j++)
			{
				if(use[j] or b[j].first==-1)continue;
				ld val=1ll*og[j].second*(l+1) - 1ll*og[j].first*(i);
				if(val<mi or (val==mi and (ind==-1 or og[ind].second>og[j].second or(og[ind].second==og[j].second and og[ind].first<=og[j].first))))
				{
					mi=val;
					ind=j;
				}
			}
			if(ind==-1)
			{
			  fk=1;
			  break;
			}
			use[ind]=1;
		// 	cout<<"using "<<ind<<" at "<<i<<endl;
		// 	cur+=(og[ind].second/(ld)i);
			tpl.push_back(og[ind].second);
		}
		if(fk)continue;
		sort(begin(tpl),end(tpl));
		for(int i=1;i<=l;i++)
		{
		  cur+=(tpl[i-1]/(ld)i);
		}
		ld sm=0;
		int tlk=k-l;
		for(int j=0;j<n and tlk>0;j++)
		{
			if(use[a[j].second])continue;
			sm+=a[j].first;
			tlk--;
		}
		ans=min(ans,cur+(sm/(l+1)));
	}
	cout<<fixed<<ans<<endl;
}

Compilation message (stderr)

Main.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main()
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23