Submission #56794

#	Time	Username	Problem	Language	Result	Execution time	Memory
56794		youngyojun	Sure Bet (CEOI17_sure)	C++11	100 / 100	182 ms	16964 KiB

sure

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;

const ld EPS = 1e-9;
const int MAXN = 100005;

ll A[MAXN], B[MAXN];

ll Ans;
int N;

ll f(int a, int b) {
	return min(A[a], B[b]);
}

ll getAns(int X) {
	int s = max(1, X-N), e = min(N, X-1);
	for(int m; s < e;) {
		m = (s+e)/2;
		ll t1 = f(m, X-m), t2 = f(m+1, X-m-1);
		if(t1 < t2) s = m+1;
		else e = m;
	}
	return f(s, X-s);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		ld a, b; cin >> a >> b;
		A[i] = a*10000 + EPS;
		B[i] = b*10000 + EPS;
	}

	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++) {
		A[i] += A[i-1];
		B[i] += B[i-1];
	}

	for(int i = 2; i <= N*2; i++)
		upmax(Ans, getAns(i) - ll(i)*10000);
	
	printf("%.4Lf\n", ld(Ans)/10000 + EPS);
	return 0;
}

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