Submission #71871

#	Time	Username	Problem	Language	Result	Execution time	Memory
71871		bnahmad15	Sure Bet (CEOI17_sure)	C++17	100 / 100	137 ms	17596 KiB

sure

#include <bits/stdc++.h>
#define forn(i,j,n) for(int i = (int)j;i<=(int)n;i++)
#define nfor(i,j,n) for(int i = (int)j;i>=(int)n;i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 100001,LOG = 17;

int n;
double a[N],b[N],sum[N],dp[N];

int main(){

	scanf("%d",&n);
	forn(i,1,n){
		scanf("%lf%lf",&a[i],&b[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	reverse(a+1,a+1+n);
	reverse(b+1,b+1+n);
	sum[1] = b[1];
	forn(i,2,n)
		sum[i] = sum[i-1] + b[i];
	double res = 0.0;
	double tmp1 = 0.0;
	forn(i,1,n){
		tmp1 -= 1.0;
		tmp1 += a[i];
		int l = 1,r = n,ret = n;
		while(l <= r){
			int md = (l+r)/2;
			tmp1 -= md;
			double tmp2 = sum[md] - i - md;
			if(tmp2 >= tmp1){
				ret = md;
				r = md - 1;
			}else{
				l = md + 1;
			}
			tmp1 += md;
		}
		double one;
		one = tmp1 - ret;
		one = min(one,sum[ret] - i - ret);
		res = max(res,one);
		if(ret > 1){
			ret--;
			one = tmp1 - ret;
			one = min(one,sum[ret] - i - ret);
			res = max(res,one);
			ret++;
		}
		if(ret < n){
			ret++;
			one = tmp1 - ret;
			one = min(one,sum[ret] - i - ret);
			res = max(res,one);
			ret--;
		}
	}
	printf("%.4lf",res);
	return 0;
}

Compilation message (stderr)

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

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