Submission #726850

#	Time	Username	Problem	Language	Result	Execution time	Memory
726850		penguin133	Sure Bet (CEOI17_sure)	C++17	100 / 100	110 ms	6732 KiB

sure

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long double A[100005], B[100005], P[100005];

void solve(){
	int n; cin >> n;
	for(int i=1;i<=n;i++)cin >> A[i] >> B[i];
	sort(A+1, A+n+1);
	sort(B+1, B+n+1);
	for(int i=n;i>=1;i--)P[i] = P[i+1] + B[i];
	long double ans = 0, cur = 0;
	for(int i=n;i>=1;i--){
		long double cur2 = 0;
		cur += A[i];
		int lo = 1, hi = n, brr = n + 1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			long double crr = min(cur, P[mid]) - (n - i + 1 + n - mid + 1);
			long double drr = min(cur, P[mid-1]) - (n - i + 1 + n - mid + 2);
			if(crr <= drr)brr = mid, hi = mid - 1;
			else lo = mid + 1;
			ans = max({ans, crr, drr});
		}
		
	}
	cout << fixed << setprecision(4) << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

sure.cpp: In function 'void solve()':
sure.cpp:24:15: warning: unused variable 'cur2' [-Wunused-variable]
   24 |   long double cur2 = 0;
      |               ^~~~
sure.cpp:26:23: warning: variable 'brr' set but not used [-Wunused-but-set-variable]
   26 |   int lo = 1, hi = n, brr = n + 1;
      |                       ^~~
sure.cpp: At global scope:
sure.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~

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