Submission #685013

#	Time	Username	Problem	Language	Result	Execution time	Memory
685013		Nuraly_Serikbay	Sure Bet (CEOI17_sure)	C++14	100 / 100	83 ms	5184 KiB

sure

/* Speech to the young */

//#include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>

/*
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
 

using namespace std;

#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
#define int long long
#define cube (x) ((x) * (x) * (x))

int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
void pre(int a) { cout<<fixed<<setprecision(a); }
int bitcount (int x) {return __builtin_popcount	(x);}

const int N = 2e6 + 10;
const int INF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int P = 31;
const double eps = 1e-19;
long double pi = 3.1415926535897323;

double a[N], b[N], res, suma[N], sumb[N];
int n;

void Solution () {
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i] >> b[i];
	sort (a + 1, a + n + 1), reverse (a + 1, a + n + 1);
	sort (b + 1, b + n + 1), reverse (b + 1, b + n + 1);
	for (int i = 1; i <= n; ++ i) {
		suma[i] = suma[i - 1] + a[i];
		sumb[i] = sumb[i - 1] + b[i];
	}
	
	
	for (int i = 1; i <= n; ++ i) {
		int l = 1, r = n, ans = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (sumb[mid] >= suma[i]) {
				r = mid - 1;
				ans = mid;
			} else l = mid + 1;
		}	
		if (ans != -1) res = max (res, (double)(suma[i] - (double)(ans + i)));
	}
	for (int i = 1; i <= n; ++ i) {
		int l = 1, r = n, ans = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (suma[mid] >= sumb[i]) {
				ans = mid;
				r = mid - 1;
			} else l = mid + 1;
		}
		if (ans != -1) res = max (res, (double)(sumb[i] - (double)(ans + i)));
	}
	cout << fixed << setprecision (4) << res;
	return; 
}

signed main () {
	YOSIK();
//	precalc();
	int T = 1;
//	cin >> T;
	while (T --) Solution ();
	exit (0);
}

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