#779231 (C++17) No.2009 Drunkers' Contest

• 問題: No.2009 Drunkers' Contest
• ユーザー: bin101
• 提出日時: 2022-07-16 17:45:13
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 47 ms / 2,000 ms
• コード長: 14,523 bytes
• コンパイル時間: 3,945 ms
• コンパイル使用メモリ: 230,756 KB
• 実行使用メモリ: 24,292 KB
• 最終ジャッジ日時: 2023-09-11 03:06:16
• 合計ジャッジ時間: 8,516 ms
• ジャッジサーバーID （参考情報）: judge14 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,380 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	2 ms; 4,384 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	1 ms; 4,380 KB
testcase_09	AC	2 ms; 4,384 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	2 ms; 4,380 KB
testcase_12	AC	2 ms; 4,376 KB
testcase_13	AC	1 ms; 4,376 KB
testcase_14	AC	2 ms; 4,380 KB
testcase_15	AC	2 ms; 4,380 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	AC	2 ms; 4,380 KB
testcase_18	AC	3 ms; 4,380 KB
testcase_19	AC	2 ms; 4,380 KB
testcase_20	AC	2 ms; 4,376 KB
testcase_21	AC	2 ms; 4,380 KB
testcase_22	AC	3 ms; 4,376 KB
testcase_23	AC	3 ms; 4,384 KB
testcase_24	AC	41 ms; 9,320 KB
testcase_25	AC	41 ms; 9,236 KB
testcase_26	AC	41 ms; 9,328 KB
testcase_27	AC	42 ms; 9,376 KB
testcase_28	AC	41 ms; 9,308 KB
testcase_29	AC	41 ms; 9,396 KB
testcase_30	AC	41 ms; 9,348 KB
testcase_31	AC	41 ms; 9,312 KB
testcase_32	AC	41 ms; 9,292 KB
testcase_33	AC	40 ms; 9,312 KB
testcase_34	AC	38 ms; 9,388 KB
testcase_35	AC	40 ms; 9,384 KB
testcase_36	AC	40 ms; 9,316 KB
testcase_37	AC	40 ms; 9,580 KB
testcase_38	AC	39 ms; 9,240 KB
testcase_39	AC	40 ms; 9,252 KB
testcase_40	AC	40 ms; 9,316 KB
testcase_41	AC	40 ms; 9,312 KB
testcase_42	AC	40 ms; 9,584 KB
testcase_43	AC	40 ms; 9,236 KB
testcase_44	AC	38 ms; 9,260 KB
testcase_45	AC	39 ms; 9,572 KB
testcase_46	AC	35 ms; 9,380 KB
testcase_47	AC	47 ms; 24,292 KB
testcase_48	AC	47 ms; 24,224 KB
testcase_49	AC	46 ms; 22,980 KB
testcase_50	AC	45 ms; 23,680 KB
testcase_51	AC	46 ms; 22,780 KB
testcase_52	AC	41 ms; 16,684 KB
testcase_53	AC	43 ms; 16,980 KB
testcase_54	AC	43 ms; 15,660 KB
testcase_55	AC	35 ms; 10,288 KB
testcase_56	AC	35 ms; 9,924 KB
testcase_57	AC	43 ms; 17,396 KB

ソースコード

#include<bits/stdc++.h> 
using namespace std;
using ll=long long int;
using Int=__int128;
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> constexpr int bitUP(T x,int a){return (x>>a)&1;}
//→　↓　←　↑ 
int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0};
//右上から時計回り
//int dh[8]={-1,0,1,1,1,0,-1,-1}, dw[8]={1,1,1,0,-1,-1,-1,0};
long double EPS = 1e-6;
long double PI = acos(-1);
const ll INF=(1LL<<62);
const int MAX=(1<<30);
//constexpr ll MOD=1000000000+7;
constexpr ll MOD=998244353;


inline void bin101(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
}

using pii=pair<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;
using pII=pair<Int,Int>;

using Graph=vector<vector<int>>;

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (size_t i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}
//pair cin
inline istream &operator>>(istream &is,Int &x) {
    string s;
    is>>s;
    x=parse(s);
	return is;
}

template<typename T >
struct edge {
	int to;
	T cost;
	edge()=default;
	edge(int to, T cost) : to(to), cost(cost) {}

};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;

template<typename T>
void CinGraph(int M,WeightGraph<T> &g,bool directed=false,bool index1=true){
    while(M--){
        int s,t;
        T cost;
        cin>>s>>t>>cost;
        if(index1) s--,t--;
        g[s].emplace_back(t,cost);
        if(not directed) g[t].emplace_back(s,cost);
    }
}

void CinGraph(int M,Graph &g,bool directed=false,bool index1=true){
    while(M--){
        int s,t;
        cin>>s>>t;
        if(index1) s--,t--;
        g[s].push_back(t);
        if(not directed) g[t].push_back(s);
    }
}


//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<T> &v) {
    for(size_t i=0;i<v.size();i++) is>>v[i];
	return is;
}
 
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        is>>v[i];
    }
    return is;
}
//vector cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<T> &v) {
    bool sp=true;
    if(string(typeid(T).name())=="c") sp=false;
    for(size_t i=0;i<v.size();i++){
        if(i and sp) os<<" ";
        os<<v[i];
    }
    return os;
}
//vector<vector> cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        os<<v[i];
        if(i+1!=v.size()) os<<"\n";
    }
    return os;
}

//Graph out
template<typename T>
inline ostream &operator<<(ostream &os,const Graph &g) {
    for(size_t i=0;i<g.size();i++){
        for(int to:g[i]){
            os<<i<<"->"<<to<<" ";
        }
        os<<endl;
    }
    return os;
}

//WeightGraph out
template<typename T>
inline ostream &operator<<(ostream &os,const WeightGraph<T> &g) {
    for(size_t i=0;i<g.size();i++){
        for(auto e:g[i]){
            os<<i<<"->"<<e.to<<"("<<e.cost<<") ";
        }
        os<<endl;
    }
    return os;
}


//要素数n 初期値x
template<typename T>
inline vector<T> vmake(size_t n,T x){
	return vector<T>(n,x);
}

//a,b,c,x data[a][b][c] 初期値x
template<typename... Args>
auto vmake(size_t n,Args... args){
	auto v=vmake(args...);
	return vector<decltype(v)>(n,move(v));
}
template<typename V,typename T>
void fill(V &v,const T value){
    v=value;
}

template<typename V,typename T>
void fill(vector<V> &vec,const T value){
    for(auto &v:vec) fill(v,value);
}

//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
	os<<p.first<<" "<<p.second;
	return os;
}
 
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
	is>>p.first>>p.second;
	return is;
}
 
//ソート
template<typename T>
inline void vsort(vector<T> &v){
    sort(v.begin(),v.end());
}
 
//逆順ソート
template<typename T>
inline void rvsort(vector<T> &v){
	sort(v.rbegin(),v.rend());
}

//1ビットの数を返す
inline int popcount(int x){
	return __builtin_popcount(x);
}
//1ビットの数を返す
inline int popcount(ll x){
	return __builtin_popcountll(x);
}
template<typename T>
inline void Compress(vector<T> &C){
    sort(C.begin(),C.end());
    C.erase(unique(C.begin(),C.end()),C.end());
}
template<typename T>
inline int lower_idx(const vector<T> &C,T value){
    return lower_bound(C.begin(),C.end(),value)-C.begin();
}
template<typename T>
inline int upper_idx(const vector<T> &C,T value){
    return upper_bound(C.begin(),C.end(),value)-C.begin();
}
//時計回りに90度回転
template<typename T>
inline void rotate90(vector<vector<T>> &C){
    vector<vector<T>> D(C[0].size(),vector<T>(C.size()));
    for(int h=0;h<C.size();h++){
        for(int w=0;w<C[h].size();w++){
            D[w][C.size()-1-h]=C[h][w];
        }
    }
    C=D;
}
//補グラフを返す
//i→iのような辺は加えない
Graph ComplementGraph(const Graph &g){
    size_t sz=g.size();
    bool used[sz][sz];
    fill(used[0],used[sz],false);
    for(size_t i=0;i<sz;i++){
        for(int to:g[i]){
            used[i][to]=true;
        }
    }
    Graph ret(sz);
    for(size_t i=0;i<sz;i++){
        for(size_t j=0;j<sz;j++){
            if(used[i][j]) continue;
            if(i==j) continue;
            ret[i].push_back(j);
        }
    }
    return ret;
}
//グラフの分解 secondはある頂点がどこに対応するか id[i]={2,3}のとき,頂点iはret[2][3]に対応
//無効グラフのみに対応
pair<vector<Graph>,vector<pair<int,int>>> GraphDecomposition(const Graph &g){
    vector<pair<int,int>> id(g.size(),pair<int,int>(-1,-1));
    vector<Graph> ret;
    vector<int> now;
    for(size_t i=0;i<g.size();i++){
        if(id[i].first!=-1) continue;
        id[i].first=ret.size();
        id[i].second=0;
        now.push_back(i);
        for(size_t j=0;j<now.size();j++){
            for(int to:g[now[j]]){
                if(id[to].first==-1){
                    id[to].first=ret.size();
                    id[to].second=now.size();
                    now.push_back(to);
                }
            }
        }
        Graph r(now.size());
        for(size_t j=0;j<now.size();j++){
            r[j]=g[now[j]];
            for(int &to:r[j]){
                to=id[to].second;
            }
        }
        ret.push_back(r);
        now.clear();
    }
    return make_pair(ret,id);
}
//0indexを想定
bool OutGrid(ll h,ll w,ll H,ll W){
    return (h>=H or w>=W or h<0 or w<0);
}

void NO(){
    cout<<"NO"<<"\n";
}
void YES(){
    cout<<"YES"<<"\n";
}
void No(){
    cout<<"No"<<"\n";
}
void Yes(){
    cout<<"Yes"<<"\n";
}
namespace overflow{
    template<typename T>
    T max(){
        return numeric_limits<T>::max();
    }
    template<typename T>
    T ADD(T a,T b){
        T res;
        return __builtin_add_overflow(a,b,&res)?max<T>():res;
    }
    template<typename T>
    T MUL(T a,T b){
        T res;
        return __builtin_mul_overflow(a,b,&res)?max<T>():res;
    }
};
using namespace overflow;
struct mint{
    using u64=uint_fast64_t;
    u64 a;
    constexpr mint() :a(0){}
    constexpr mint(ll x) :a((x>=0)?(x%MOD):(x%MOD+MOD) ) {}

    inline constexpr mint operator+(const mint rhs)const noexcept{
        return mint(*this)+=rhs;
    }
    inline constexpr mint operator-(const mint rhs)const noexcept{
        return mint(*this)-=rhs;
    }
    inline constexpr mint operator*(const mint rhs)const noexcept{
        return mint(*this)*=rhs;
    }
    inline constexpr mint operator/(const mint rhs)const noexcept{
        return mint(*this)/=rhs;
    }
    inline constexpr mint operator+(const ll rhs) const noexcept{
        return mint(*this)+=mint(rhs);
    }
    inline constexpr mint operator-(const ll rhs)const noexcept{
        return mint(*this)-=mint(rhs);
    }
    inline constexpr mint operator*(const ll rhs)const noexcept{
        return mint(*this)*=mint(rhs);
    }
    inline constexpr mint operator/(const ll rhs)const noexcept{
        return mint(*this)/=mint(rhs);
    }

    inline constexpr mint &operator+=(const mint rhs)noexcept{
        a+=rhs.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    inline constexpr mint &operator-=(const mint rhs)noexcept{
        if(rhs.a>a) a+=MOD;
        a-=rhs.a;
        return *this;
    }
    inline constexpr mint &operator*=(const mint rhs)noexcept{
        a=(a*rhs.a)%MOD;
        return *this;
    }
    inline constexpr mint &operator/=(mint rhs)noexcept{
        a=(a*rhs.inverse().a)%MOD;
        return *this;
    }
    inline constexpr mint &operator+=(const ll rhs)noexcept{
        return *this+=mint(rhs);
    }
    inline constexpr mint &operator-=(const ll rhs)noexcept{
        return *this-=mint(rhs);
    }
    inline constexpr mint &operator*=(const ll rhs)noexcept{
        return *this*=mint(rhs);
    }
    inline constexpr mint &operator/=(const ll rhs)noexcept{
        return *this/=mint(rhs);
    }

    inline constexpr mint operator=(const ll x)noexcept{
        a=(x>=0)?(x%MOD):(x%MOD+MOD);
        return *this;
    }

    inline constexpr bool operator==(const mint p)const noexcept{
        return a==p.a;
    }

    inline constexpr bool operator!=(const mint p)const noexcept{
        return a!=p.a;
    }

    inline constexpr mint pow(ll N) const noexcept{
        mint ans(1LL),p(a);
        while(N>0){
            if(bitUP(N,0)){
                ans*=p;
            }
            p*=p;
            N>>=1;
        }
        return ans;
    }
    inline constexpr mint inverse() const noexcept{
        return pow(MOD-2);
    }

};
inline constexpr mint operator+(const ll &a,const mint &b)noexcept{
    return mint(a)+=b;
}
inline constexpr mint operator-(const ll &a,const mint &b)noexcept{
    return mint(a)-=b;
}
inline constexpr mint operator*(const ll &a,const mint &b)noexcept{
    return mint(a)*=b;
}
inline constexpr mint operator/(const ll &a,const mint &b)noexcept{
    return mint(a)/=b;
}
//cout
inline ostream &operator<<(ostream &os,const mint &p) {
    return os<<p.a;
}

//cin
inline istream &operator>>(istream &is,mint &p) {
    ll t;
    is>>t;
    p=t;
    return is;
}

struct Binominal{
    vector<mint> fac,finv,inv; //fac[n]:n! finv:(n!)の逆元
    int sz;
    Binominal(int n=10) :sz(1){
        if(n<=0) n=10;
        init(n);
    }
    inline void init(int n){
        fac.resize(n+1,1);
        finv.resize(n+1,1);
        inv.resize(n+1,1);
        for(int i=sz+1;i<=n;i++){
            fac[i]=fac[i-1]*i;
            inv[i]=MOD-inv[MOD%i]*(MOD/i);
            finv[i]=finv[i-1]*inv[i];
        }
        sz=n;
    }
    //nCk(n,k<=N) をO(1)で求める
    inline mint com(int n,int k){
        if(n<k) return mint(0);
        if(n<0 || k<0) return mint(0);
        if(n>sz) init(n);
        return fac[n]*finv[k]*finv[n-k];
    }
    //nCk(k<=N) をO(k)　で求める 
    inline mint rcom(ll n,int k){
        if(n<0 || k<0 || n<k) return mint(0);
        if(k>sz) init(k);
        mint ret(1);
        for(int i=0;i<k;i++){
            ret*=n-i;
        }
        ret*=finv[k];
        return ret;
    }

    //重複組み合わせ n種類のものから重複を許してk個を選ぶ
    //〇がn個,|がk個
    inline mint h(int n,int k){
        return com(n+k-1,k);
    }
    //順列の公式
    inline mint P(int n,int k){
        if(n<k) return 0;
        if(n>sz) init(n);
        return fac[n]*finv[n-k];
    }

};
vector<int> Subset(int S,bool zero=false,bool full=false){
    vector<int> ret;
    int now=(S-1)&S;
    if(full and S){
        ret.push_back(S);
    }
    do{
        ret.push_back(now);
        now=(now-1)&S;
    }while(now!=0);
    if(zero){
        ret.push_back(0);
    }
    return ret;
}
template<typename T>
T SUM(const vector<T> &v,int s,int t){
    chmax(s,0);
    chmin(t,int(v.size())-1);
    if(s>t) return 0;
    if(s==0) return v[t];
    else return v[t]-v[s-1];
}
template<typename T>
void buildSUM(vector<T> &v){
    for(size_t i=1;i<v.size();i++){
        v[i]+=v[i-1];
    }
    return;
}

//erase_vertexの頂点を消して
//インデックスを調整したグラフを返す
Graph EraseVertex(Graph graph,vector<int> erase_vertex){
    vector<bool> erase(graph.size(),false);
    vector<int> sum(graph.size(),0);
    int cnt_erase=0;
    for(int idx:erase_vertex){
        if(erase[idx]) continue;
        cnt_erase++;
        erase[idx]=true;
        sum[idx]++;
    }
    for(int i=1;i<(int)sum.size();i++){
        sum[i]+=sum[i-1];
    }
    for(int i=0;i<int(graph.size())-cnt_erase;i++){
        int pre_i=i+sum[i];
        graph[i].clear();
        for(int to:graph[pre_i]){
            if(erase[to]) continue;
            graph[i].push_back(to-sum[to]);
        }
    }
    return graph;
}

void solve(){
    int N;
    cin>>N;
    vector<Int> A(N),B(N);
    cin>>A>>B;
    stack<pII> S;

    for(int i=0;i<N;i++){
        auto a=A[i],b=B[i];

        while(S.size()){
            Int sa,sb;
            tie(sa,sb)=S.top();
            if(sa*b>=a*sb){
                a+=sa;
                b+=sb;
                S.pop();
            }else{
                break;
            }
        }
        S.emplace(a,b);
    }
    vector<pII> v;
    while(S.size()){
        v.emplace_back(S.top());
        S.pop();
    }
    reverse(ALL(v));
    using DD=long double;
    DD ans=0;
    for(auto p:v){
        DD x=sqrt(DD(p.first)/p.second)-1;
        chmax(x,0);
        ans+=p.first/(1+x)+p.second*(1+x);
    }
    cout<<ans<<endl;
}

int main(){
    bin101();
    int T=1;
    //cin>>T;
    while(T--) solve();
}