Submission #113892

#TimeUsernameProblemLanguageResultExecution timeMemory
113892Mahdi_JfriSure Bet (CEOI17_sure)C++14
100 / 100
127 ms6780 KiB
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define ld long double

const int maxn = 1e5 + 20;

ld res , sum[maxn] , a[maxn] , b[maxn];

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

	reverse(a + 1 , a + n + 1);
	reverse(b + 1 , b + n + 1);

	for(int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + b[i];

	ld s = 0;
	for(int i = 1; i <= n; i++)
	{
		s += a[i];
		int k = lower_bound(sum , sum + n + 1 , s) - sum;
		if(k > n + 1)
			k--;
		res = max(res , min(sum[k] , s) - k - i);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	for(int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];

	solve(n);

	for(int i = 1; i <= n; i++)
		swap(a[i] , b[i]);
	
	solve(n);

	cout << fixed << setprecision(4) << res << endl;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...