제출 #142820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
142820		lyc	Sure Bet (CEOI17_sure)	C++14	100 / 100	113 ms	3320 KiB

sure

#define DEBUG
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

#ifdef DEBUG
    #define DBG(...) __VA_ARGS__
#else
    #define DBG(...)
#endif

const int MAXN = 1e5+5;
int N;
int A[MAXN]; ll B[MAXN];

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N){
        double a, b; cin >> a >> b;
        A[i] = (int)round(a*10000), B[i] = (ll)round(b*10000);
        A[i] -= 10000, B[i] -= 10000;
    }

    sort(A+1,A+1+N,greater<int>());
    sort(B+1,B+1+N,greater<ll>());
    FOR(i,1,N) B[i] += B[i-1];

    ll ans = 0, x = 0;
    FOR(i,0,N) {
        x += A[i];

        int lo = 0, hi = N+1;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            if (x-mid*10000 >= B[mid]-i*10000) lo = mid+1;
            else hi = mid;
        }
        int idx = lo-1;
        //cout << i << " :: idx " << idx << " x y " << x-idx*10000 << " " << B[idx]-i*10000 << endl;
        ans = max(ans, min(x-idx*10000, B[idx]-i*10000));
        //if (idx+1 <= N) cout << i << " :: idx " << idx << " x y " << x-(idx+1)*10000 << " " << B[idx+1]-i*10000 << endl;
        if (idx+1 <= N) ans = max(ans, min(x-(idx+1)*10000, B[idx+1]-i*10000));
    }
    cout << fixed << setprecision(4) << (double)ans/10000 << '\n';
}

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