結果

問題 No.3318 客に卵をかける
コンテスト
ユーザー のらら
提出日時 2025-08-15 15:32:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,998 bytes
コンパイル時間 3,426 ms
コンパイル使用メモリ 190,796 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-26 11:39:34
合計ジャッジ時間 3,596 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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 =long 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 ff = [&](ll y)->classMat{
    ll takoyaki = X + Y * y;
    ll l = 1, r = N - y;
    vector<vector<classMat>> a = {{1.0 - 1.0 / takoyaki, 1.0}, {0.0, 1.0}};
    vector<vector<classMat>> b = {{(classMat)0, 0}, {(classMat)Q, 0}};
    auto f = [&](ll x)->classMat{
      vector<vector<classMat>> c = mat_pow(a, x);
      vector<vector<classMat>> chk = mat_mul(c, b);
      return (classMat)P * y + ((classMat)Q - (classMat)R / takoyaki) * (N - y - x) + chk[0][0];
    };
    while(r - l > 2){
      ll m1 = (l * 2 + r) / 3;
      ll m2 = (l + r * 2) / 3;
      if(f(m1) < f(m2)) l = m1;
      else r = m2;
    }
    classMat ret = 0.0;
    for(ll j = l; j <= r; j++){
      ret = max(ret, f(j));
    }
    return ret;
  };
  ll l2 = 0, r2 = N - 1;
  while(r2 - l2 > 2){
    ll mm1 = (l2 * 2 + r2) / 3;
    ll mm2 = (l2 + r2 * 2) / 3;
    if(ff(mm1) < ff(mm2)) l2 = mm1;
    else r2 = mm2;
  }
  classMat ans = 0.0;
  for(ll i = l2; i <= r2; i++){
    ans = max(ans, ff(i));
  }
  cout << fixed << setprecision(15) << ans << endl;
  return 0;
}
0