Submission #94531

#	Time	Username	Problem	Language	Result	Execution time	Memory
94531		jasony123123	Sure Bet (CEOI17_sure)	C++11	0 / 100	2 ms	376 KiB

sure

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e12;
/***************************CEOI 17 Day 1 P2 - Sure Bet*************************************/
const int MX = 1e5 + 99;

int N;
ll A[MX], B[MX];

ll opt(int X) {
	int loA = max(0, X - N), hiA = min(X, N);

	int lo = loA, hi = hiA;
	while (lo<hi) { // find first time A>=B
		int mid = (hi + lo) / 2;
		if (A[mid] < B[X - mid]) lo = mid + 1;
		else hi = mid;
	}

	ll ans = 0;
	FORE(betsA, lo - 5, lo + 5) if (loA <= betsA && betsA <= hiA)
		maxx(ans, min(A[betsA], B[X - betsA]) - X*10000LL);
	return ans;
}

int main() {
	io();
	cin >> N;
	FORE(i, 1, N) {
		double a, b; cin >> a >> b;
		A[i] = (ll)(a*1e4), B[i] = (ll)(b*1e4);
	}
	sort(A+1, A + N+1, greater<ll>()), sort(B+1, B + N+1, greater<ll>());
	FORE(i, 2, N)
		A[i] += A[i - 1], B[i] += B[i - 1];
	
	ll ans = 0;
	FORE(x, 1, 2 * N) maxx(ans, opt(x));
	cout << fixed << setprecision(4) << (double)ans/1e4 << "\n";
}

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