oj.uz

Submission #237809

# Submission time Handle Problem Language Result Execution time Memory
237809 2020-06-08T22:02:18 Z eohomegrownapps Sure Bet (CEOI17_sure) C++14
0 / 100
 5 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);}
	}
	cout<<fixed<<setprecision(4)<<maxval<<'\n';
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 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 5 ms 384 KB Output is correct
2 Incorrect 5 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 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -