結果

問題 No.3318 客に卵をかける
コンテスト
ユーザー GOTKAKO
提出日時 2025-10-31 23:23:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 626 ms / 2,000 ms
コード長 2,118 bytes
コンパイル時間 1,856 ms
コンパイル使用メモリ 196,408 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-31 23:23:10
合計ジャッジ時間 3,989 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while(T--){
        long long N,X,Y,P,Q,R; cin >> N >> X >> Y >> P >> Q >> R;
        /*double answer = 0;
        for(long long up=0; up<=N; up++,X+=Y){
            double now = P*up;
            int n = N-up;
            vector<double> dp(n+1);
            for(int i=1; i<=n; i++){
                double v = 1.0/X*max(Q+0.0,Q-R+dp.at(i-1))+(1-1.0/X)*(Q+dp.at(i-1));
                dp.at(i) = v;
            }
            now += dp.at(n);
            cout << fixed << setprecision(20) << up << " " << now << "\n";
            answer = max(answer,now);
        }*/
        auto f = [&](long long up) -> long double {
            long long n = N-up;
            long double ng = 1.0/(X+Y*up),ok = 1-ng;
            auto f2 = [&](long long stop) -> long double {
                long long work = n-stop;
                long double ret = work*(ok*Q+ng*(Q-R));
                ret += 1/ng*Q;
                long double allok = 1,ok2 = ok;
                while(stop){
                    if(stop&1) allok *= ok2;
                    ok2 *= ok2,stop >>= 1;
                }
                ret -= 1/ng*Q*allok;
                return ret;
            };
            long long low = 0,high = n+1;
            while(high-low > 2){
                long long mid1 = (low+low+high)/3,mid2 = (low+high+high)/3;
                if(f2(mid1) < f2(mid2)) low = mid1;
                else high = mid2;
            }
            long double ret = -1e18;
            for(long long i=low; i<high; i++) ret = max(ret,f2(i));
            ret += up*P;
            return ret;
        };
        long long low = 0,high = N+1;
        while(high-low > 2){
            long long mid1 = (low+low+high)/3,mid2 = (low+high+high)/3;
            if(f(mid1) < f(mid2)) low = mid1;
            else high = mid2;
        }
        long double answer = -1e18;
        for(long long i=low; i<high; i++) answer = max(answer,f(i));
        cout << fixed << setprecision(20) << answer << "\n";
    }
}
0