제출 #1353548

#제출 시각아이디문제언어결과실행 시간메모리
1353548goulthenSure Bet (CEOI17_sure)C++20
100 / 100
36 ms3156 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 5e5+10;
const int INF = 1e18+10;
const int MOD = 1e9+7;
double a[MAXN], b[MAXN];

void solve() {
    int n; cin >> n;
    rep(i,1,n) {
        cin >> a[i] >> b[i];
    }
    sort(a+1,a+n+1, greater<double>());
    sort(b+1,b+n+1, greater<double>());
    rep(i,1,n) a[i] += a[i-1];
    rep(i,1,n) b[i] += b[i-1];
    double ans = 0;
    priority_queue<double> pq;
    int j = 1;
    rep(x,1,n) {
        while (j<=n && b[j]<=a[x]) {
            pq.push(b[j]-j);
            j++;
        }
        if(pq.size()>0) ans = max(ans, pq.top()-x);
        if(j<=n) ans = max(ans, a[x]-x-j);
    }

    cout << fixed << setprecision(4) << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int tt = 1;
    //cin >> tt;
    
    while(tt--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...