Submission #704266

#	Time	Username	Problem	Language	Result	Execution time	Memory
704266		ld_minh4354	Let's Win the Election (JOI22_ho_t3)	C++17	23 / 100	2556 ms	336 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"



signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int n,i,a[505],b[505],m,cnt,max_p,cnt0,cy[505],cn[505],size_cy,size_cn;
	long double sum,ans;
	bool tr;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>a[i]>>b[i];
	
	max_p=1;
	for (i=1;i<n+1;i++) max_p*=2;
	max_p--;
	
	ans=1e9;
	for (cnt=0;cnt<max_p;cnt++)
	{
		cnt0=cnt;
		size_cy=size_cn=0;tr=true;
		
		for (i=1;i<n+1;i++)
		{
			if (cnt0%2==0)
			{
				size_cn++;
				cn[size_cn]=a[i];
			}
			else
			{
				size_cy++;
				cy[size_cy]=b[i];
				if (b[i]==-1) tr=false;
			}
			
			cnt0/=2;
		}
		
		if (size_cy<=m and tr)
		{
			sort(cn+1,cn+size_cn+1);
			sort(cy+1,cy+size_cy+1);
			sum=0;
			
			for (i=1;i<size_cy+1;i++) sum += (double)cy[i]/i;
			for (i=1;i<=m-size_cy;i++) sum += (double)cn[i]/(size_cy+1);
			
			ans=min(ans,sum);
		}
	}
	
	cout<<fixed<<setprecision(4)<<ans;
		
}

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