oj.uz

Submission #997807

# Submission time Handle Problem Language Result Execution time Memory
997807 2024-06-12T22:56:38 Z amirhoseinfar1385 Sure Bet (CEOI17_sure) C++17
100 / 100
 593 ms 3668 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n;
vector<double>psa,psb,alla,allb;

void vorod(){
	cin>>n;
	alla.resize(n);
	allb.resize(n);
	for(int i=0;i<n;i++){
		cin>>alla[i]>>allb[i];
	}
}

void pre(){
	sort(allb.rbegin(),allb.rend());
	sort(alla.rbegin(),alla.rend());
	psa.resize(n);
	psb.resize(n);
	psa[0]=alla[0];
	psb[0]=allb[0];
	for(int i=1;i<n;i++){
		psa[i]=psa[i-1]+alla[i];
		psb[i]=psb[i-1]+allb[i];
	}
}

void solve(){
	double res=0;
	for(int i=1;i<=n*2;i++){
		double low=0,high=1000*i+1,mid;
		for(int j=0;j<50;j++){
			mid=(high+low)/2;
			mid+=i;
			int pa=lower_bound(psa.begin(),psa.end(),mid)-psa.begin();
			int pb=lower_bound(psb.begin(),psb.end(),mid)-psb.begin();
			if(pa==(int)psa.size()||pb==(int)psb.size()){
				high=mid-i;
				continue;
			}
			if(pa+pb+2<=i){
				low=mid-i;
				continue;
			}
			high=mid-i;
		}
		res=max(res,low);
	}
	cout<<setprecision(4)<<fixed<<res<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	pre();
	solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 4 ms 488 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 565 ms 3588 KB Output is correct
18 Correct 561 ms 3664 KB Output is correct
19 Correct 579 ms 3416 KB Output is correct
20 Correct 548 ms 3572 KB Output is correct
21 Correct 575 ms 3668 KB Output is correct
22 Correct 538 ms 3584 KB Output is correct
23 Correct 557 ms 3416 KB Output is correct
24 Correct 581 ms 3412 KB Output is correct
25 Correct 555 ms 3588 KB Output is correct
26 Correct 593 ms 3408 KB Output is correct