oj.uz

Submission #54920

# Submission time Handle Problem Language Result Execution time Memory
54920 2018-07-05T12:01:39 Z Mamnoon_Siam Sure Bet (CEOI17_sure) C++17
100 / 100
 812 ms 17760 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

typedef long long ll;

ll scale = 10000;

ll read() {
	string s; cin >> s;
	for(char &b : s) if(b == '.') b = ' ';
	stringstream is(s);
	string x, y;
	is >> x; is >> y;
	while(y.size() < 4) y += "0";
	ll xx, yy;
	is = stringstream(x); is >> xx;
	is = stringstream(y); is >> yy;
	return xx * scale + yy;
}

const int maxn = 100010;

vector<ll> L, R, LR;
int n;

ll solve(int k) {
	ll final = 0;
	int ret = -1, lo = 0, hi = min(n, k);
	while(lo <= hi) {
		int mid = lo + hi >> 1;
		int rem = min(k - mid, n);
		if(L[mid] > R[rem]) {
			hi = mid - 1;
		} else {
			ret = mid;
			lo = mid + 1;
		}
	} assert(ret != -1);
	final = L[ret];
	ret = -1, lo = 0, hi = min(n, k);
	while(lo <= hi) {
		int mid = lo + hi >> 1;
		int rem = min(k - mid, n);
		if(R[mid] > L[rem]) {
			hi = mid - 1;
		} else {
			ret = mid;
			lo = mid + 1;
		}
	} assert(ret != -1);
	final = max(final, R[ret]);
	return final - scale * k;
	// ll ret = -1e18;
	// for(int i = 0; i <= min(k, n); i++) {
	// 	ret = max(ret, min(L[i], R[min(n, k - i)]));
	// } return ret - k * scale;
}

ll gen(ll i, ll took, ll x, ll y) {
	if(i == n) return min(x, y) - took * scale;
	ll ret = 0;
	ret = max(ret, gen(i + 1, took, x, y));
	ret = max(ret, gen(i + 1, took + 1, x + L[i], y));
	ret = max(ret, gen(i + 1, took + 1, x, y + R[i]));
	ret = max(ret, gen(i + 1, took + 2, x + L[i], y + R[i]));
	return ret;
}

int32_t main () {
	cout << fixed << setprecision(4);
	cin >> n;
	L.resize(n), R.resize(n);
	for(int i = 0; i < n; i++) {
		L[i] = read();
		R[i] = read();
		//cout << L[i] << ' ' << R[i] << endl;
	}
	//cout << (double)gen(0, 0, 0, 0) / double(scale) << endl;
	sort(all(L)), sort(all(R));
	reverse(all(L)), reverse(all(R));
	for(int i = 1; i < n; i++) L[i] += L[i - 1], R[i] += R[i - 1];
	L.insert(L.begin(), 0); R.insert(R.begin(), 0);
	ll mx = -1e18;
	for(int i = 0; i <= (n << 1); i++) {
		mx = max(mx, solve(i));
	} cout << double(mx) / double(scale) << endl;
}

Compilation message

sure.cpp: In function 'int myrand(int, int)':
sure.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
sure.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
sure.cpp: In function 'll solve(int)':
sure.cpp:57:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~
sure.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 4 ms 548 KB Output is correct
11 Correct 4 ms 548 KB Output is correct
12 Correct 12 ms 568 KB Output is correct
13 Correct 9 ms 628 KB Output is correct
14 Correct 8 ms 660 KB Output is correct
15 Correct 10 ms 696 KB Output is correct
16 Correct 12 ms 800 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 4 ms 548 KB Output is correct
11 Correct 4 ms 548 KB Output is correct
12 Correct 12 ms 568 KB Output is correct
13 Correct 9 ms 628 KB Output is correct
14 Correct 8 ms 660 KB Output is correct
15 Correct 10 ms 696 KB Output is correct
16 Correct 12 ms 800 KB Output is correct
17 Correct 689 ms 4560 KB Output is correct
18 Correct 738 ms 5932 KB Output is correct
19 Correct 779 ms 7300 KB Output is correct
20 Correct 642 ms 8796 KB Output is correct
21 Correct 812 ms 10548 KB Output is correct
22 Correct 753 ms 11684 KB Output is correct
23 Correct 770 ms 13144 KB Output is correct
24 Correct 760 ms 14596 KB Output is correct
25 Correct 659 ms 15880 KB Output is correct
26 Correct 716 ms 17760 KB Output is correct