Submission #127008

#	Time	Username	Problem	Language	Result	Execution time	Memory
127008		Lawliet	Sure Bet (CEOI17_sure)	C++14	100 / 100	220 ms	6088 KiB

sure

#include <bits/stdc++.h>
 
#define MAX 100010
 
using namespace std;
 
int n;
 
double ans = -4000000.0;
 
double a[MAX];
double b[MAX];
double ansA[MAX];
double ansB[MAX];
double mxAnsB[MAX];

bool test(double k)
{
	for(int qtdA = 0 ; qtdA <= n ; qtdA++)
	{
		double aux = ansA[qtdA] - k;

		//printf("===== qtdA = %d      %lf\n",qtdA,aux);

		if(ansA[qtdA] < k) continue;

		int mxQtdB = floor( aux );
		mxQtdB = min(mxQtdB , n);

		//printf("----------------- qtdA = %d        mxQtdB = %d\n",qtdA,mxQtdB);

		if(mxAnsB[ mxQtdB ] - qtdA >= k) return true;
	}

	return false;
}

double bs()
{
	double l = 0, r = 200000000.0;

	for(int cnt = 0 ; cnt <= 500 ; cnt++)
	{
		double m = (l + r)/2;

		//printf("l = %lf  r = %lf  m = %lf\n",l,r,m);

		if(test(m)) l = m;
		else r = m;
	}

	return l;
}

void init()
{
	sort(a + 1 , a + n + 1);
	sort(b + 1 , b + n + 1);

	for(int g = 1 ; g <= n ; g++)
	{
		ansA[g] = ansA[g - 1] + a[n - g + 1];
		ansB[g] = ansB[g - 1] + b[n - g + 1];

		//printf("g = %d        ansA = %lf\n",g,ansA[g]);
	}

	for(int g = 1 ; g <= n ; g++)
	{
		ansA[g] -= g;
		ansB[g] -= g;

		mxAnsB[g] = max(mxAnsB[g - 1] , ansB[g]);
	}


}
 
int main()
{
	scanf("%d",&n);
 
	for(int g = 1 ; g <= n ; g++)
		scanf("%lf %lf",&a[g],&b[g]);
 
	init();
 
	printf("%.4lf\n",bs());
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
sure.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf %lf",&a[g],&b[g]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40