Submission #800956

#TimeUsernameProblemLanguageResultExecution timeMemory
800956vjudge1Sure Bet (CEOI17_sure)C++98
100 / 100
79 ms5180 KiB
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define el '\n'
#define fi first
#define sc second
//#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
//#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
//using namespace __gnu_pbds;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e5+11;
// find_by_order, order_of_key
int n;
ld a[N], b[N];
void sol()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    sort(a, a+n);
    sort(b, b+n);
    reverse(a, a+n);
    reverse(b, b+n);
    int id=0;
    ld ans1=0, ans2=0, ans=0;
    for(int i=0;i<n;i++)
    {
        ans1 += a[i];
        while(id<n && min(ans1-id, ans2-i-1) < min(ans1-id-1, ans2+b[id]-i-1))
        {
            ans2 += b[id];
            id++;
        }
        ans = max(ans, min(ans1-id, ans2-i-1));
    }
    cout << fixed << setprecision(4) << ans;
}
signed main()
{
//    freopen("SUREBET.INP", "r", stdin);
//    freopen("SUREBET.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...