# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1027314 |
2024-07-19T03:34:01 Z |
vjudge1 |
Sure Bet (CEOI17_sure) |
C++17 |
|
2000 ms |
4444 KB |
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define yy cout<<"YES"<<endl;
#define nn cout<<"NO"<<endl;
#define ld long double
#define T ll t;cin>>t;while(t--){solve();}
#define funfact for(ll i=1 ; i<=n ; i++){cout<<a[i]<<" ";}
using namespace std;
const ll N=2e5,mod=1e9+7,inf=1e18;
ld a[N],b[N];
ld prea[N],preb[N];
ll n;
//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------//
bool cmp (ld x,ld y)
{
return x>y;
}
ld f(ll x,ll y)
{
return min(prea[x]-1.0*y,preb[y]-1.0*x);
}
ld bin(ll x)
{
ll l=1,r=n;
ld ans=-1;
if(n == 1) return f(x, 1);
if(n == 2) return max(f(x, 1), f(x, 2));
while (l<=r)
{
ll md=(l+r)/2;
ll fi=md-1,se=md,th=md+1;
if (fi==0)
{
ans=md,l=md+1;
continue;
}
if (th==n+1)
{
ans=md,r=md-1;
continue;
}
if (f(x,fi)<f(x,se)&&f(x,se)>f(x,th))
{
ans=md,l=md+1;
}
else if (f(x,fi)>f(x,se)&&f(x,se))
{
ans=md,r=md-1;
}
else if (f(x,fi)<f(x,se)&&f(x,se)>f(x,th))
{
return f(x,se);
}
}
return f(x,ans);
}
void solve(){
cin>>n;
for (ll i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
a[i]--;
b[i]--;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
ld ans=0.0;
for (ll i=1;i<=n;i++){
prea[i]+=prea[i-1]+a[i];
preb[i]+=preb[i-1]+b[i];}
for (ll i=n;i>=1;i--)
{
ans=max(ans,bin(i));
}
cout<<fixed<<setprecision(4)<<ans<<endl;
}
int main(){
solve();
}
/* This code is created by anhluong
-------Copy code is prohibiited in any form
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Execution timed out |
2037 ms |
4440 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Execution timed out |
2037 ms |
4440 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Execution timed out |
2037 ms |
4440 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |