oj.uz

Submission #237810

# Submission time Handle Problem Language Result Execution time Memory
237810 2020-06-08T22:03:19 Z eohomegrownapps Sure Bet (CEOI17_sure) C++14
0 / 100
 4 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long double ld;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	vector<ld> vals1(n);
	vector<ld> vals2(n);
	vector<ld> pref1(n+1);
	vector<ld> pref2(n+1);
	vector<ld> prefind1(n+1);
	vector<ld> prefind2(n+1);
	for (int i = 0; i<n; i++){
		cin>>vals1[i]>>vals2[i];
	}
	sort(vals1.rbegin(),vals1.rend());
	sort(vals2.rbegin(),vals2.rend());
	for (int i = 1; i<=n; i++){
		pref1[i]=pref1[i-1]+vals1[i-1]-1;
		prefind1[i]=pref1[i]+i;
		pref2[i]=pref2[i-1]+vals2[i-1]-1;
		prefind2[i]=pref2[i]+i;
	}
	ld maxval = 0;
	for (int i = 0; i<=n; i++){
		//smallest x such that prefind1[i]<prefind2[x]
		int lb = lower_bound(prefind2.begin(),prefind2.end(),prefind1[i])-prefind2.begin();
		if (lb!=n){maxval=max(maxval,pref1[i]-lb);}
		int ub = lb-1;
		if (ub!=-1){maxval=max(maxval,pref2[ub]-i);}
	}
	printf("%.4lf",(double)maxval);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -