oj.uz

Submission #94532

# Submission time Handle Problem Language Result Execution time Memory
94532 2019-01-19T22:41:21 Z jasony123123 Sure Bet (CEOI17_sure) C++11
100 / 100
 109 ms 3584 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 416 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 416 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 51 ms 3324 KB Output is correct
18 Correct 53 ms 3192 KB Output is correct
19 Correct 54 ms 3192 KB Output is correct
20 Correct 54 ms 3392 KB Output is correct
21 Correct 58 ms 3584 KB Output is correct
22 Correct 51 ms 3192 KB Output is correct
23 Correct 51 ms 3220 KB Output is correct
24 Correct 52 ms 3320 KB Output is correct
25 Correct 109 ms 3392 KB Output is correct
26 Correct 58 ms 3576 KB Output is correct