oj.uz

Submission #160606

# Submission time Handle Problem Language Result Execution time Memory
160606 2019-10-28T18:18:06 Z shashwatchandra Sure Bet (CEOI17_sure) C++17
100 / 100
 293 ms 8364 KB 
/*input
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 1e5+1;
double a[N];
double b[N];
double pref1[N];
double pref2[N];
int n;

bool cmp(double x,double y){
	return x > y;
}


void solve(){
  	cin >> n;
  	RE(i,n)cin >> a[i] >> b[i];
  	sort(a+1,a+n+1,cmp);
  	sort(b+1,b+n+1,cmp);
  	pref1[0] = pref2[0] = 0;
  	RE(i,n){
  		pref1[i] = pref1[i-1]+a[i];
  		pref2[i] = pref2[i-1]+b[i];
  		//cout << i << " " << pref1[i] << " " << pref2[i] << endl;
  	}
  	double ans = 0;
  	REP(i,n+1){
  		double term1 = pref1[i]-i;
  		double term2 = -(double)i;
  		int lo = 0;
  		int hi = n;
  		if(cmp(term1-lo,term2+pref2[lo]-lo) == cmp(term1-hi,term2+pref2[hi]-hi)){
  			double op1 = min(term1-lo,term2+pref2[lo]-lo);
  			double op2 = min(term1-hi,term2+pref2[hi]-hi);
  			ans = max(ans,max(op1,op2));
  			continue;
  		}
  		bool ini = cmp(term1-lo,term2+pref2[lo]-lo);
  		while(lo < hi){
  			int mid = (lo+hi)/2;
  			bool here = cmp(term1-mid,term2+pref2[mid]-mid);
  			if(here == ini)lo = mid+1;
  			else hi = mid;
  		}
  		//cout << "WOW " << i << " " << lo << " ";
  		hi = lo;
  		lo--;
  		double op1 = min(term1-lo,term2+pref2[lo]-lo);
  		double op2 = min(term1-hi,term2+pref2[hi]-hi);
  		ans = max(ans,max(op1,op2));
  		//cout << max(op1,op2) << endl;
  	}
  	cout << fixed << setprecision(4) << ans;
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 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 3 ms 376 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 3 ms 504 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 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 3 ms 376 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 152 ms 8112 KB Output is correct
18 Correct 153 ms 8108 KB Output is correct
19 Correct 157 ms 7964 KB Output is correct
20 Correct 149 ms 7964 KB Output is correct
21 Correct 160 ms 8364 KB Output is correct
22 Correct 150 ms 7932 KB Output is correct
23 Correct 151 ms 8012 KB Output is correct
24 Correct 152 ms 7904 KB Output is correct
25 Correct 293 ms 7928 KB Output is correct
26 Correct 166 ms 8312 KB Output is correct