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

提出ソース

結果

問題	No.2009 Drunkers' Contest
ユーザー	bin101
提出日時	2022-07-16 17:36:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	13,673 bytes
コンパイル時間	2,889 ms
コンパイル使用メモリ	232,668 KB
実行使用メモリ	13,808 KB
最終ジャッジ日時	2024-06-28 17:29:10
合計ジャッジ時間	8,878 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	3 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	3 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	5 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	AC	51 ms 6,784 KB
testcase_45	AC	52 ms 6,656 KB
testcase_46	AC	39 ms 6,656 KB
testcase_47	AC	41 ms 13,804 KB
testcase_48	AC	41 ms 13,808 KB
testcase_49	AC	40 ms 13,076 KB
testcase_50	AC	41 ms 13,416 KB
testcase_51	AC	40 ms 13,188 KB
testcase_52	AC	37 ms 10,428 KB
testcase_53	AC	43 ms 10,124 KB
testcase_54	AC	43 ms 9,708 KB
testcase_55	AC	39 ms 7,168 KB
testcase_56	AC	37 ms 6,656 KB
testcase_57	AC	42 ms 10,384 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 Graph=vector<vector<int>>;

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<ll> A(N),B(N);
    cin>>A>>B;
    stack<pll> S;

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

        while(S.size()){
            ll 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<pll> v;
    while(S.size()){
        v.emplace_back(S.top());
        S.pop();
    }
    reverse(ALL(v));
    double ans=0;
    for(auto p:v){
        double x=sqrt(double(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();
}

yukicoder

結果

テストケース

ソースコード