結果

問題 No.3318 客に卵をかける
コンテスト
ユーザー のらら
提出日時 2025-08-15 14:57:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,933 bytes
コンパイル時間 3,436 ms
コンパイル使用メモリ 190,536 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-26 11:39:31
合計ジャッジ時間 3,642 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <atcoder/all>
#include <iomanip>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
ll N, X, Y, P, Q, R;

//行列積
using classMat = double;
vector<vector<classMat>> mat_mul(vector<vector<classMat>> a, vector<vector<classMat>> b) {
  int n = a.size();
  vector<vector<classMat>> res(n, vector<classMat>(n));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < n; k++){
        res[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return res;
}
//行列累乗
vector<vector<classMat>> mat_pow(vector<vector<classMat>> a, ll b) {
  int n = a.size();
  vector<vector<classMat>> res(n, vector<classMat>(n));
  for(int i = 0; i < n; i++) res[i][i] = 1.0;
  while(b){
    if(b & 1) res = mat_mul(res, a);
    a = mat_mul(a, a);
    b = (b >> 1);
  }
  return res;
}

int main(){
  cin >> N;
  cin >> X >> Y;
  cin >> P >> Q >> R;
  auto f = [&](ll x)->double{
    ll takoyaki = X + Y * x;
    ll l = 1, r = N - x;
    vector<vector<classMat>> a = {{1.0 - 1.0 / takoyaki, 1.0}, {0.0, 1.0}};
    vector<vector<classMat>> b = {{(double)0, 0}, {(double)Q, 0}};
    while(l < r){
      ll m = (l + r) / 2;
      vector<vector<classMat>> tc = mat_pow(a, m);
      vector<vector<classMat>> tchk = mat_mul(tc, b);
      if(tchk[0][0] + (Q - R) * takoyaki > Q){
        r = m;
      }else{
        l = m + 1;
      }
    }
    vector<vector<classMat>> c = mat_pow(a, l);
    vector<vector<classMat>> chk = mat_mul(c, b);
    return (double)P * x + ((double)Q - (double)R / takoyaki) * (N - x - l) + chk[0][0];
  };
  ll l2 = 0, r2 = N - 1;
  while(r2 - l2 > 2){
    ll m1 = (l2 * 2 + r2) / 3;
    ll m2 = (l2 + r2 * 2) / 3;
    if(f(m1) < f(m2)) l2 = m1;
    else r2 = m2;
  }
  double ans = 0.0;
  for(ll i = l2; i <= r2; i++){
    ans = max(ans, f(i));
  }
  cout << fixed << setprecision(15) << ans << endl;
  return 0;
}
0