Submission #1205468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205468		Mighilon	Sure Bet (CEOI17_sure)	C++20	100 / 100	55 ms	1864 KiB

sure

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;

void solve(){
    int n;
    cin>>n;
    vector<double> a(n),b(n);
    F0R(i,n){
        cin>>a[i]>>b[i];
        a[i]--; b[i]--;
    }
    sort(all(a),[](auto& i, auto& j){return i>j;});
    sort(all(b),[](auto& i, auto& j){return i>j;});
    F0R(i,n-1)
        b[i+1]+=b[i];
    pair<double,double> ans={0,0};
    double x=0;
    auto f=[&](int i,int j){
        return min(x-(j+1),b[j]-(i+1));
    };
    F0R(i,n){
        x+=a[i];
        int l=-1,r=n;
        while(r-l>1){
            int mid=(r+l)>>1;
            if(f(i,mid)>f(i,mid+1)){
                r=mid;
            }
            else{
                l=mid;
            }
        }
        l++;
        if(min(x-(l+1),b[l]-(i+1))>min(ans.f,ans.s))
            ans={x-(l+1),b[l]-(i+1)};
    }
    cout<<fixed<<setprecision(4)<<min(ans.f,ans.s)<<nl;
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40