제출 #1149492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149492		dosts	Sure Bet (CEOI17_sure)	C++20	0 / 100	7 ms	14404 KiB

sure

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 3e5+1,MOD = 998244353,BL = 1000;

int n,m,threshold;
vi edges[N],tin(N),tout(N),dp(N);
int up[N][20];
int timer = 1;
void dfs(int node,int p) {
    tin[node] = timer++;
    up[node][0] = p;
    for (int i=1;i<20;i++) up[node][i] = up[up[node][i-1]][i-1];
    for (auto it : edges[node]) {
        if (it == p) continue;
        dfs(it,node);
    }
    tout[node] = timer-1;
} 

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tin[b] <= tout[a];
}

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i = 19;i>=0;i--) {
        if (!anc(up[a][i],b)) a = up[a][i];
    }
    return up[a][0];
}

void dfs2(int node,int p) {
    for (auto it : edges[node]) {
        if (it == p) continue;
        dfs2(it,node);
        dp[node]+=dp[it];
    }
}
void solve() { 
    int n;
    cin >> n;
    vector<double> odds(n),odds2(n);
    for (auto& it : odds) cin >> it;
    for (auto& it : odds2) cin >> it;
    sort(all(odds),greater<double>()),sort(all(odds2),greater<double>());
    vector<double> suf(n+1,0);
    for (int i=1;i<=n;i++) suf[i] = suf[i-1]+odds2[i-1];
    double ans = 0;
    double s = 0;
    cout << fixed;
    cout << setprecision(12);
    for (int i=0;i<=n;i++) {
        s+=odds[i-1];
        double l = 0;
        double r = inf;
        double eps = 1e-6;
        while (l+eps<r) {
            double v = (l+r)/2;
            //x <= s-v-i
            //s[x]-x >= v+i olan son x
            int l1 = 0;
            int r1 = n;
            while (l1 <= r1) {
                int m1 = (l1+r1) >> 1;
                if (suf[m1] >= v+i+m1 && s >= v+i+m1) l1 = m1+1;
                else r1 = m1-1;
            }
            if (r1 >= 0) l = v+eps;
            else r = v-eps;
        }
        ans = max(ans,r);
    }
    cout << setprecision(4) << ans;
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
    freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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