oj.uz

Submission #598916

# Submission time Handle Problem Language Result Execution time Memory
598916 2022-07-19T07:36:37 Z denniskim Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 1 ms 468 KB 
#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 = 10000000000000;
		
		won[i] = a[i].fi;
		a[i].se = i;
	}
	assert(k <= 5);
	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 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

Main.cpp: In function 'int main()':
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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -