Submission #94532

#	Time	Username	Problem	Language	Result	Execution time	Memory
94532		jasony123123	Sure Bet (CEOI17_sure)	C++11	100 / 100	109 ms	3584 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;
}

ll parse(string x) {
	int pos = x.find('.');
	int num0 = x.size() - 1 - pos;
	FOR(i, 0, 4 - num0) x.push_back('0');
	x.erase(x.find('.'), 1);
	return stoll(x);
}

int main() {
	io();
	cin >> N;
	FORE(i, 1, N) {
		string a, b; cin >> a >> b;
		A[i] = parse(a), B[i] = parse(b);
	}
//	darr(A, N + 1);
	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];
	
	//darr(A, N + 1);
	//darr(B, N + 1);
	ll ans = 0;
	FORE(x, 1, 2 * N) {
	//	cout << x << ": " << opt(x) << "\n";
		maxx(ans, opt(x));
	}
//	cout << ans << "\n";

	cout << fixed << setprecision(4) << (double)ans/1e4 << "\n";
}

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