Submission #859952

#	Time	Username	Problem	Language	Result	Execution time	Memory
859952		StefanSebez	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	27 ms	520 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int inf=1e9;
int main()
{
    int n,k;cin>>n>>k;
    pair<int,int>a[n+1];
    multiset<pair<int,int> >st1,st2;
    for(int i=1;i<=n;i++)
	{
		cin>>a[i].se>>a[i].fi;
		if(a[i].fi!=-1)st1.insert(a[i]);
		st2.insert({a[i].se,a[i].fi});
	}
    sort(a+1,a+n+1);
    long double res=inf;
    for(int j=0;j<=k;j++)
	{
		int K=k,J=j;
		long double sum=0,c=1;
		multiset<pair<int,int> >ST1,ST2;
		ST1=st1;
		ST2=st2;
		while(!ST1.empty() && J>0)
		{
			pair<int,int>x=*ST1.begin();
			if(x.fi!=-1)
			{
				sum+=(long double)x.fi/c;
				c++;
				J--;
				K--;
				ST2.erase(ST2.find({x.se,x.fi}));
			}
			ST1.erase(ST1.find(x));
		}
		while(!ST2.empty() && K>0)
		{
			pair<int,int>x=*ST2.begin();
			sum+=(long double)x.fi/c;
			if(x.fi==x.se) c++;
			K--;
			ST2.erase(ST2.find(x));
		}
		if(res>sum)
		{
			res=sum;
		}
	}
	cout<<setprecision(9)<<fixed;
	cout<<res;
	return 0;
}

• 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