結果

問題 No.2158 X日後に全完するhibit君
コンテスト
ユーザー kotamanegi
提出日時 2022-12-05 23:40:09
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,315 bytes
コンパイル時間 2,027 ms
コンパイル使用メモリ 164,584 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 19:49:19
合計ジャッジ時間 2,930 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:17: warning: using directive refers to implicitly-defined namespace 'std'
    1 | using namespace std;
      |                 ^
1 warning generated.

ソースコード

diff # 

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

#define REP(a, b) for (long long a = 0; a < b; ++a)
#define ALL(a) begin(a), end(a)

#define ld long double
#define int long long
vector<tuple<int, int, int>> inputs;
const ld eps = 1e-12;
int n, k;
ld cnts[6 * 6 * 6 * 6 * 6 * 6];
int steps[6 * 6 * 6 * 6 * 6 * 6];
const int bo[6] = {1, 6, 36, 216, 1296, 7776};

ld dfs(int now)
{
  if (cnts[now] == -1)
  {
    steps[now] = 1;
    cnts[now] = 1;
    int cry[6] = {};
    int go = now;
    REP(q, n)
    {
      cry[q] = go % 6;
      go /= 6;
    }

    for (int q = 0; q < (1 << n); ++q)
    {
      ld prob = 1;
      int costs = 0;
      int next_now = now;
      REP(j, n)
      {
        if (q & (1 << j))
        {
          // take new points.
          prob *= (ld)(get<0>(inputs[j]) - cry[j]) / (ld)(get<0>(inputs[j]) - k);
          next_now += bo[j];
          costs += get<1>(inputs[j]);
        }
        else
        {
          // take bad points.
          prob *= (ld)(cry[j] - k) / (ld)(get<0>(inputs[j]) - k);
          costs += get<2>(inputs[j]);
        }
      }
      if (prob == 0.0)
        continue;
      if (costs > 60)
      {
        cnts[now] += dfs(next_now) * prob;
        steps[now] = max(steps[now], steps[next_now] + 1);
      }
    }
  }
  return cnts[now];
}

void solve()
{
  cin >> n >> k;
  REP(i, n)
  {
    int a, b, c;
    cin >> a >> b >> c;
    inputs.push_back({a, b, c});
  }
  REP(i, 6 * 6 * 6 * 6 * 6 * 6)
  {
    cnts[i] = -1;
  }
  tuple<int, int, ld> ans;
  int smallest = 0;
  int largest = 0;
  REP(i, n)
  {
    smallest += get<1>(inputs[i]);
    largest += get<2>(inputs[i]);
  }
  if (largest > 60)
  {
    cout << -1 << endl;
    return;
  }

  if (smallest <= 60)
  {
    cout << "1 1 1" << endl;
    return;
  }
  else
  {
    get<0>(ans) = k + 2;
  }
  int now = 0;
  REP(i, n)
  {
    now += bo[i] * k;
  }
  get<2>(ans) = dfs(now) + k;
  get<1>(ans) = k + steps[now];
  cout << get<0>(ans) << " " << get<1>(ans) << " " << get<2>(ans) << endl;
}

#undef int

int main()
{
  // Fasterize input/output script
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(100);

  int t = 1;
  // cin >> t; // comment out if solving multi testcase
  for (int testCase = 1; testCase <= t; ++testCase)
  {
    solve();
  }
  return 0;
}
0