Submission #598890

#	Time	Username	Problem	Language	Result	Execution time	Memory
598890		denniskim	Let's Win the Election (JOI22_ho_t3)	C++17	21 / 100	1499 ms	460 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second

ll n;
ll k;
pair< pair<ll, ll>, ll> a[510];
pair<ll, ll> won[510];
ld ans = INF;
ll chk[510];

ld calc(void)
{
	vector<ll> aa, bb;
	ld ret = 0;
	ll ppl = 1;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		if(chk[i] == 1)
			aa.push_back({won[i].se});
		else if(chk[i] == 2)
			bb.push_back({won[i].fi});
	}
	
	sort(bb.begin(), bb.end());
	
	for(auto &i : bb)
	{
		ret += (ld)i / (ld)ppl;
		ppl++;
	}
	
	for(auto &i : aa)
		ret += (ld)i / (ld)ppl;
	
	return ret;
}

int main(void)
{
	scanf("%lld", &n);
	scanf("%lld", &k);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		scanf("%lld %lld", &a[i].fi.se, &a[i].fi.fi);
		
		if(a[i].fi.fi == -1)
			a[i].fi.fi = 1000000000000;
		
		won[i] = a[i].fi;
		a[i].se = i;
	}
	
	sort(a + 1, a + 1 + n);
	
	for(ll i = 1 ; i <= k ; i++)
		chk[a[i].se] = 2;
	
	for(ll i = 0 ; i <= k ; i++)
	{
		vector<ll> vec;
		vector< pair< pair<ll, ll>, ll> > vec2;
		ld minn = INF;
		ll gap1, gap2;
		ll A = i, B = k - i;
		ll mini = INF, ww = 0;
		ll ad = 0, sb = 0;
		
		ans = min(ans, calc());
		
		for(ll j = 1 ; j <= n ; j++)
		{
			if(chk[a[j].se] == 2)
				vec.push_back(j);
			
			else if(!chk[a[j].se])
			{
				if(mini > a[j].fi.se)
				{
					mini = a[j].fi.se;
					ww = j;
				}
			}
		}
		
		for(auto &j : vec)
		{
			chk[a[j].se] = 0;
			chk[a[j].se] = 1;
			
			ld gappp = calc();
			
			if(minn > gappp)
			{
				minn = gappp;
				ad = a[j].se;
				sb = a[j].se;
			}
			
			chk[a[j].se] = 2;
			
			if(ww)
			{
				chk[a[j].se] = 0;
				chk[a[ww].se] = 1;
				
				gappp = calc();
				
				if(minn > gappp)
				{
					minn = gappp;
					ad = a[ww].se;
					sb = a[j].se;
				}
				
				chk[a[j].se] = 2;
				chk[a[ww].se] = 0;
			}
		}
		
		chk[sb] = 0;
		chk[ad] = 1;
	}
	
	ans = min(ans, calc());
	
	printf("%.10Lf", ans);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:74:6: warning: unused variable 'gap1' [-Wunused-variable]
   74 |   ll gap1, gap2;
      |      ^~~~
Main.cpp:74:12: warning: unused variable 'gap2' [-Wunused-variable]
   74 |   ll gap1, gap2;
      |            ^~~~
Main.cpp:75:6: warning: unused variable 'A' [-Wunused-variable]
   75 |   ll A = i, B = k - i;
      |      ^
Main.cpp:75:13: warning: unused variable 'B' [-Wunused-variable]
   75 |   ll A = i, B = k - i;
      |             ^
Main.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%lld", &k);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%lld %lld", &a[i].fi.se, &a[i].fi.fi);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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