Submission #954487

#	Time	Username	Problem	Language	Result	Execution time	Memory
954487		mocha	Sure Bet (CEOI17_sure)	C++14	100 / 100	94 ms	6732 KiB

sure

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;

int n;
long double a[mx], b[mx];
long double ans = 0;
long double sa = 0;
long double d[mx];

int main() {
	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n;
	for (int i=0;i<n;i++) {
		cin >> a[i] >> b[i];
	}
	sort(a, a+n); reverse(a, a+n);
	sort(b, b+n); reverse(b, b+n);
	d[0] = b[0];
	for (int i=1;i<n;i++) {
		d[i] = d[i-1] + b[i];
	}
	for (int i=0;i<n;i++) {
		sa += a[i];
		if (a[i] <= 1) break;
		long double sb = 0;
	//	for (int j=0;j<n;j++) {
	//		cout << sa - i - j - 2 << " ";
	//	}
	//	cout << "\n";
		int lc = 0, rc = n-1;
		while (lc < rc) {
			int m = lc + rc >> 1;
			if ((sa - i - m - 2) < (d[m] - i - m - 2)) {
				rc = m;
			} else {
				lc = m+1;
			}
		}
	//	cout << lc << " ";
		long double tmp;
		tmp = min(sa - i - lc - 2, d[lc] - i - lc - 2);
		if ( lc != 0 ) {
			tmp = max(tmp, min(sa - i - lc - 1, d[lc-1] - i - lc - 1));
		}
		ans = max(ans, tmp);
  	}
//	cout << "\n";
	cout << fixed << setprecision(4) << ans << "\n";
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |    int m = lc + rc >> 1;
      |            ~~~^~~~
sure.cpp:27:15: warning: unused variable 'sb' [-Wunused-variable]
   27 |   long double sb = 0;
      |               ^~

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