oj.uz

Submission #71871

# Submission time Handle Problem Language Result Execution time Memory
71871 2018-08-25T18:03:19 Z bnahmad15 Sure Bet (CEOI17_sure) C++17
100 / 100
 137 ms 17596 KB 
#include <bits/stdc++.h>
#define forn(i,j,n) for(int i = (int)j;i<=(int)n;i++)
#define nfor(i,j,n) for(int i = (int)j;i>=(int)n;i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 100001,LOG = 17;

int n;
double a[N],b[N],sum[N],dp[N];

int main(){

	scanf("%d",&n);
	forn(i,1,n){
		scanf("%lf%lf",&a[i],&b[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	reverse(a+1,a+1+n);
	reverse(b+1,b+1+n);
	sum[1] = b[1];
	forn(i,2,n)
		sum[i] = sum[i-1] + b[i];
	double res = 0.0;
	double tmp1 = 0.0;
	forn(i,1,n){
		tmp1 -= 1.0;
		tmp1 += a[i];
		int l = 1,r = n,ret = n;
		while(l <= r){
			int md = (l+r)/2;
			tmp1 -= md;
			double tmp2 = sum[md] - i - md;
			if(tmp2 >= tmp1){
				ret = md;
				r = md - 1;
			}else{
				l = md + 1;
			}
			tmp1 += md;
		}
		double one;
		one = tmp1 - ret;
		one = min(one,sum[ret] - i - ret);
		res = max(res,one);
		if(ret > 1){
			ret--;
			one = tmp1 - ret;
			one = min(one,sum[ret] - i - ret);
			res = max(res,one);
			ret++;
		}
		if(ret < n){
			ret++;
			one = tmp1 - ret;
			one = min(one,sum[ret] - i - ret);
			res = max(res,one);
			ret--;
		}
	}
	printf("%.4lf",res);
	return 0;
}

Compilation message

sure.cpp: In function 'int main()':
sure.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
sure.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 3 ms 684 KB Output is correct
6 Correct 3 ms 688 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 4 ms 376 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 3 ms 684 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 4 ms 700 KB Output is correct
10 Correct 3 ms 708 KB Output is correct
11 Correct 3 ms 752 KB Output is correct
12 Correct 4 ms 756 KB Output is correct
13 Correct 4 ms 756 KB Output is correct
14 Correct 3 ms 804 KB Output is correct
15 Correct 3 ms 836 KB Output is correct
16 Correct 3 ms 1056 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 4 ms 376 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 3 ms 684 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 4 ms 700 KB Output is correct
10 Correct 3 ms 708 KB Output is correct
11 Correct 3 ms 752 KB Output is correct
12 Correct 4 ms 756 KB Output is correct
13 Correct 4 ms 756 KB Output is correct
14 Correct 3 ms 804 KB Output is correct
15 Correct 3 ms 836 KB Output is correct
16 Correct 3 ms 1056 KB Output is correct
17 Correct 137 ms 4620 KB Output is correct
18 Correct 92 ms 5968 KB Output is correct
19 Correct 94 ms 7304 KB Output is correct
20 Correct 103 ms 8616 KB Output is correct
21 Correct 94 ms 10476 KB Output is correct
22 Correct 85 ms 11960 KB Output is correct
23 Correct 111 ms 13212 KB Output is correct
24 Correct 103 ms 14696 KB Output is correct
25 Correct 92 ms 15944 KB Output is correct
26 Correct 97 ms 17596 KB Output is correct