結果

問題 No.5003 物理好きクリッカー
ユーザー koyumeishikoyumeishi
提出日時 2018-12-05 06:01:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 9,285 ms / 10,000 ms
コード長 27,910 bytes
コンパイル時間 2,881 ms
実行使用メモリ 118,264 KB
スコア 279,494,948,854
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 08:47:59
合計ジャッジ時間 269,980 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7,612 ms
116,464 KB
testcase_01 AC 7,809 ms
116,248 KB
testcase_02 AC 8,483 ms
116,448 KB
testcase_03 AC 7,236 ms
116,656 KB
testcase_04 AC 8,336 ms
118,264 KB
testcase_05 AC 7,910 ms
116,924 KB
testcase_06 AC 8,994 ms
117,404 KB
testcase_07 AC 8,123 ms
117,344 KB
testcase_08 AC 9,285 ms
117,608 KB
testcase_09 AC 7,651 ms
117,000 KB
testcase_10 AC 8,146 ms
117,584 KB
testcase_11 AC 8,702 ms
116,852 KB
testcase_12 AC 7,568 ms
116,408 KB
testcase_13 AC 7,567 ms
116,564 KB
testcase_14 AC 7,520 ms
115,976 KB
testcase_15 AC 7,917 ms
116,816 KB
testcase_16 AC 8,008 ms
116,612 KB
testcase_17 AC 7,592 ms
116,808 KB
testcase_18 AC 7,970 ms
116,476 KB
testcase_19 AC 7,815 ms
117,296 KB
testcase_20 AC 8,349 ms
117,612 KB
testcase_21 AC 7,821 ms
117,148 KB
testcase_22 AC 8,213 ms
117,188 KB
testcase_23 AC 8,581 ms
117,284 KB
testcase_24 AC 7,711 ms
117,152 KB
testcase_25 AC 7,514 ms
116,764 KB
testcase_26 AC 8,571 ms
116,976 KB
testcase_27 AC 7,793 ms
116,256 KB
testcase_28 AC 7,057 ms
116,496 KB
testcase_29 AC 7,288 ms
116,372 KB
testcase_30 AC 8,090 ms
116,984 KB
testcase_31 AC 8,274 ms
117,232 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#pragma GCC optimize ("-Ofast")

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
#include <memory>
#include <unordered_map>
#include <array>
#include <numeric>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}

namespace timer{
  using namespace chrono;
  steady_clock::time_point start_time;
  unsigned long long begin_time;
  unsigned long long int get_cycle()
  {
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
  }

  void init(){
    start_time = steady_clock::now();
    begin_time = get_cycle();
  }

  double sec_per_cycle(){
    auto end_time = steady_clock::now();
    double elapsed = duration_cast<nanoseconds>(end_time - start_time).count() * 1e-9;
    return elapsed / (get_cycle() - begin_time);
  }

  // [sec]
  double get()
  {
    static double spc = sec_per_cycle();
    return (double)(get_cycle() - begin_time) * spc;
  }

};

class XorShift{
public:
  uint32_t x;
  uint32_t y;
  uint32_t z;
  uint32_t w;

  XorShift(){
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = 88675123;
  }
  
  XorShift(uint32_t seed){
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = seed;

    for(int i=0; i<100; i++){
      next();
    }
  }
  
  uint32_t next() {
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
  }

  uint32_t operator () () {
    return next();
  }

  // [0, range)
  int operator () (int range){
    return (((long long)next()) * range) >> 32 ;
  }

  // [0, 1.0]
  double prob(){
    return (next()&0xfffffff) * 3.7252903123397e-9; // 0xfffffff = 268,435,455 = 2^28-1
  }

  template<class T>
  T& operator()(vector<T>& v){
    return v[ next()%v.size() ];
  }

  template<class T>
  void shuffle(vector<T>& v){
    int n = v.size();
    for(int i=0; i<n; i++){
      int j = (*this)(n-i) + i;
      swap(v[i], v[j]);
    }
  }
};

XorShift rng(114514);

using Int = int64_t; // __int128 ?

enum class Facility{
  CLICK = 0,
  HAND = 1,
  LILY = 2,
  FACTORY = 3,
  CASINO = 4,
  GRIMOIRE = 5,
  NONE = 6
};

enum class Command{
  CLICK = 0,
  BUY = 1,
  SELL = 2,
  REINFORCE = 3,
  ENHCLICK = 4,
  NOTHING = 5
};

constexpr int num_facilities = 6;
constexpr int num_commands = 6;

array<string, num_facilities> facility_name{
  "click"s,
  "hand"s,
  "lily"s,
  "factory"s,
  "casino"s,
  "grimoire"s
};

array<string, num_commands> command_name{
  "click"s,
  "buy"s,
  "sell"s,
  "reinforce"s,
  "enhclick"s,
  "nothing"s
};

string get_command_str(Command cmd, Facility target){
  if(target == Facility::NONE){
    return command_name[(int)cmd];
  }else{
    if(target == Facility::CLICK)
      return command_name[(int)Command::ENHCLICK];
    return command_name[(int)cmd] + " " + facility_name[(int)target];
  }
}

array<vector<Int>, num_facilities> buy_price{
  vector<Int>{-1},
  vector<Int>{150},
  vector<Int>{2000},
  vector<Int>{30000},
  vector<Int>{600000},
  vector<Int>{10000000}
};

array<vector<Int>, num_facilities> enh_price{
  vector<Int>{15},
  vector<Int>{1500},
  vector<Int>{20000},
  vector<Int>{300000},
  vector<Int>{6000000},
  vector<Int>{100000000}
};

array<vector<Int>, num_facilities> prod{
  vector<Int>{1},
  vector<Int>{1},
  vector<Int>{10},
  vector<Int>{120},
  vector<Int>{2000},
  vector<Int>{25000}
};

Int next_buy_price(Int p){
  // Int hoge = (p * 6 + 4) / 5;
  // Int res =  ceil(p*6.0 / 5.0);
  // assert(res == hoge);
  // return res;
  return (p * 6 + 4) / 5;
  // return p * 12 / 10 + !!(p * 12 % 10);
}

Int get_buy_price(Facility f, int cnt){
  if((int)buy_price[(int)f].size() <= cnt){
    buy_price[(int)f].emplace_back(next_buy_price(buy_price[(int)f].back()));
  }
  return buy_price[(int)f][cnt];
}

Int next_enh_price(Int p){
  return p * 10;
}

Int get_enh_price(Facility f, int level){
  if((int)enh_price[(int)f].size() <= level){
    enh_price[(int)f].emplace_back(next_enh_price(enh_price[(int)f].back()));
  }
  return enh_price[(int)f][level];
}

Int next_prod(Int p){
  return p * 2;
}

Int get_prod(Facility f, int level){
  if((int)prod[(int)f].size() <= level){
    prod[(int)f].emplace_back(next_prod(prod[(int)f].back()));
  }
  return prod[(int)f][level];
}

struct Movement{
  int turn;
  Command cmd;
  Facility target;
  // shared_ptr<Movement> prev;
  int prev;
};
struct State{
  Int cookie = 0;
  Int cookie_prod_per_turn = 0;
  Int future_cookies = 0;
  array<int, num_facilities> facility_cnt{};
  array<int, num_facilities> facility_level{};
  // shared_ptr<Movement> movement;
  int movement = -1;
  long long hash = 0;
};


constexpr int beam_width = 500;
// constexpr int beam_width = 100;
constexpr int num_next_state = 5*3 + 3;
constexpr int same_state_limt = 1;

template<size_t L, class T>
struct my_pool{
  array<T, L> pool;
  array<int, L> idx;
  int size = 0;
  my_pool(){
    init();
  }
  void init(){
    size = 0;
    iota(idx.begin(), idx.end(), 0); 
  }
  int get(){
    return idx[size++];
  }
  void erase(int i){
    idx[--size] = i;
  }
  int set(const T& v){
    int i = get();
    pool[i] = v;
    return i;
  }
};

array<array<State, beam_width * num_next_state>, 3> beam_pool{};

array<Int, num_facilities> zhash_facility_cnt{};
array<Int, num_facilities> zhash_facility_level{};

double ww = 1.248;

class Solver{
  int n;
  string s;
  my_pool<10005 * beam_width + beam_width * num_next_state, Movement> movement_pool;
  vector<int> fever;
  vector<int> r_bonus;
  int num_check_point = 18;
  int check_point_interval;
  vector<vector<long double>> gain_coeff;

 public:
  Solver(istream& is) : movement_pool(){
    is >> n;
    is >> s;
    init();
  }

  void solve(){
    auto res = beam_search();
    for(int t=0; t<2; t++){
      auto res_d = dp(res);
      res = res_d;
    }
    output(res);
  }

 private:
  void init(){
    s = "N" + s;

    fever = vector<int>(s.size(), 0);
    for(int i=0; i<(int)s.size(); i++){
      if(s[i] == 'F'){
        fever[i] = 20;
      }
      if(i) fever[i] = max(fever[i], fever[i-1]-1);
    }
    for(int& i: fever){
      i = min(i, 1);
    }

    r_bonus = vector<int>(s.size(), 0);
    for(int i=1; i<(int)s.size(); i++){
      if(s[i] == 'B'){
        r_bonus[i-1] = 1;
      }
    }
    for(int i=s.size()-2; i>=0; i--){
      r_bonus[i] += r_bonus[i+1];
    }

    for(int i=0; i<num_facilities; i++){
      zhash_facility_level[i] = rng();
      zhash_facility_cnt[i] = rng();
    }

    check_point_interval = n / num_check_point;
    gain_coeff = vector<vector<long double>>(num_check_point, vector<long double>(s.size(), 0.0));

    for(int w=0; w<num_check_point; w++){
      int j = s.size()-1 - s.size() * w / num_check_point;
      for(int i=j-1; i>=0; i--){
        gain_coeff[w][i] = pow(1.01, r_bonus[i] - r_bonus[j]) * (fever[i]*6 + 1);
        gain_coeff[w][i] += gain_coeff[w][i + 1];
      }
    }
  }

  Int calc_future_cookies(State& state, int turn){
    turn++;
    static int check_point = 0;
    static int j = 0;

    static int i = -1;
    static double pk = 1;
    if(i != turn){
      i = turn;
      check_point = max<int>(0, num_check_point-1 - floor(turn * ww / check_point_interval ));
      j = s.size() - 1 - s.size() * check_point / check_point_interval;
      pk = pow(1.01, r_bonus[turn] - r_bonus[j]);
    }

    Int res = ceil(
      state.cookie * pk +
      gain_coeff[check_point][turn] *
      (state.cookie_prod_per_turn + get_prod(Facility::CLICK, state.facility_level[(int)Facility::CLICK]))
      );

    return res;
  }

  vector<pair<Command, Facility>> beam_search(State initial_state = State{
    0,
    0,
    0,
    {1, 0, 0, 0, 0, 0},
    {},
    -1,
    0
  }, int begin = 0, int end = 10000){
    
    vector<int> prev_beam_ids {0};
    beam_pool[begin%3][0] = initial_state;
    // beam search
    for(int i=begin; i<end; i++){
      int next_pool_size = 0;
      int next_pool_index = (i+1) % 3;

      // eprintln("turn=", i,
      //   ", cookies = ", beam_pool[i%3][prev_beam_ids[0]].cookie,
      //   ", future_cookies = ", beam_pool[i%3][prev_beam_ids[0]].future_cookies);
      // eprintln("beam_size =", prev_beam_ids.size());

      for(auto bid: prev_beam_ids){
        auto& state = beam_pool[i%3][bid];

        { // click (nothing)
          auto& next_state = beam_pool[next_pool_index][next_pool_size++];
          Int gain = get_prod(Facility::CLICK, state.facility_level[(int)Facility::CLICK]);
          if(fever[i]){
            gain *= 7;
          }
          next_state.cookie = state.cookie + gain;
          next_state.cookie_prod_per_turn = state.cookie_prod_per_turn;
          next_state.facility_cnt = state.facility_cnt;
          next_state.facility_level = state.facility_level;
          next_state.movement = movement_pool.set( Movement{
          // next_state.movement = make_shared<Movement>(Movement{
            i,
            Command::CLICK,
            Facility::NONE,
            state.movement
          });
          next_state.hash = state.hash;
        }
        { // buy
          for(int j=1; j<=5; j++){
            Int next_price = get_buy_price((Facility)j, state.facility_cnt[j]);
            if(s[i] == 'S'){
              // Int hoge = ceil(next_price * 0.9);
              // Int hoge = next_price = (next_price * 90) / 100 + !!(next_price * 90 % 100);
              next_price = (next_price * 90 + 99) / 100;
              // if(hoge != next_price){
              //   eprintln(hoge, next_price);
              // }
              // assert(hoge == next_price);
            }
            if(state.cookie < next_price) continue;

            auto& next_state = beam_pool[next_pool_index][next_pool_size++];
            next_state.cookie = state.cookie - next_price;
            next_state.cookie_prod_per_turn = state.cookie_prod_per_turn
              + get_prod((Facility)j, state.facility_level[j]);
            next_state.facility_cnt = state.facility_cnt;
            next_state.facility_cnt[j]++;
            next_state.facility_level = state.facility_level;
            next_state.movement = movement_pool.set( Movement{
            // next_state.movement = make_shared<Movement>(Movement{
              i,
              Command::BUY,
              (Facility)j,
              state.movement
            });
            next_state.hash = state.hash + zhash_facility_cnt[j];
          }
        }
        { // enhance
          for(int j=0; j<=5; j++){
            if(state.facility_cnt[j] == 0) continue;
            Int next_price = get_enh_price((Facility)j, state.facility_level[j]);
            if(s[i] == 'S'){
              // Int hoge = ceil(next_price * 0.9);
              next_price = (next_price * 90 + 99) / 100;
              // Int hoge = next_price = (next_price * 90) / 100 + !!(next_price * 90 % 100);
              // if(hoge != next_price){
              //   eprintln(hoge, next_price);
              // }
              // assert(hoge == next_price);
            }
            if(state.cookie < next_price) continue;
            Int diff = j == 0 ? 0 :
              get_prod((Facility)j, state.facility_level[j] + 1) -
              get_prod((Facility)j, state.facility_level[j]);

            auto& next_state = beam_pool[next_pool_index][next_pool_size++];
            next_state.cookie = state.cookie - next_price;
            next_state.cookie_prod_per_turn = state.cookie_prod_per_turn +
              diff * state.facility_cnt[j];
            next_state.facility_cnt = state.facility_cnt;
            next_state.facility_level = state.facility_level;
            next_state.facility_level[j]++;
            next_state.movement = movement_pool.set( Movement{
            // next_state.movement = make_shared<Movement>(Movement{
              i,
              Command::REINFORCE,
              (Facility)j,
              state.movement
            });
            next_state.hash = state.hash + zhash_facility_level[j];
          }
        }
        if( i > 9975 ){ // sell
          for(int j=1; j<=5; j++){
            if(state.facility_cnt[j] == 0) continue;
            Int sell_price = (get_buy_price((Facility)j, state.facility_cnt[j]-1) * 25 + 99) / 100;
            // Int hoge = ceil(get_buy_price((Facility)j, state.facility_cnt[j]-1) * 0.25);
            // assert(hoge == sell_price);

            auto& next_state = beam_pool[next_pool_index][next_pool_size++];
            next_state.cookie = state.cookie + sell_price;
            next_state.cookie_prod_per_turn = state.cookie_prod_per_turn -
              get_prod((Facility)j, state.facility_level[j]);
            next_state.facility_cnt = state.facility_cnt;
            next_state.facility_cnt[j]--;
            next_state.facility_level = state.facility_level;
            next_state.movement = movement_pool.set( Movement{
            // next_state.movement = make_shared<Movement>(Movement{
              i,
              Command::SELL,
              (Facility)j,
              state.movement
            });
            next_state.hash = state.hash - zhash_facility_cnt[j];
          }
        }

      }

      vector<pair<Int, int>> idx(next_pool_size);

      for(int b=0; b<next_pool_size; b++){
        auto& state = beam_pool[next_pool_index][b];
        Int gain = state.cookie_prod_per_turn;
        if(fever[i]){
          gain *= 7;
        }
        state.cookie += gain;

        if(s[i+1] == 'B'){
          // Int hoge = state.cookie + ceil(state.cookie * 0.01);

          state.cookie = (state.cookie * 101 + 99) / 100;
          // state.cookie += (state.cookie * 001 + 99) / 100;
          // assert(hoge == state.cookie);
        }

        state.future_cookies = calc_future_cookies(state, i);

        idx[b] = {-state.future_cookies, b};
      }

      int sz = min(next_pool_size, beam_width);
      // sort(idx.begin(), idx.end());

      vector<int> next_beam_ids;
      // map<Int, int> used;
      unordered_map<Int, int> used;

      // for(int j=0; j<(int)idx.size(); j++){
      //   auto& state = beam_pool[next_pool_index][idx[j].second];
      //   if(used[state.hash] == same_state_limt || (int)next_beam_ids.size() >= sz){
      //     movement_pool.erase(state.movement);
      //     continue;
      //   };
      //   next_beam_ids.emplace_back(idx[j].second);
      //   used[state.hash]++;
      // }

      int offset = 0;
      while(idx.size()){
        sz = min<int>(idx.size() - offset, beam_width - next_beam_ids.size());

        if(sz<=0){
          for(int j=0; j + offset<(int)idx.size(); j++){
            auto& state = beam_pool[next_pool_index][idx[j + offset].second];
            movement_pool.erase(state.movement);
          }
          break;
        }

        nth_element(idx.begin() + offset, idx.begin()+sz + offset, idx.end());
        sort(idx.begin() + offset, idx.begin()+sz + offset);
        for(int j=0; j<sz; j++){
          auto& state = beam_pool[next_pool_index][idx[j+offset].second];
          if(used[state.hash] == same_state_limt){
            movement_pool.erase(state.movement);
            continue;
          };
          next_beam_ids.emplace_back(idx[j+offset].second);
          used[state.hash]++;
        }

        // idx = move(decltype(idx)(idx.begin()+sz, idx.end()));
        offset += sz;
      }

      prev_beam_ids = move(next_beam_ids);
    }

    // restore commands
    {
      vector<pair<Int, int>> idx;
      auto& pool = beam_pool[end%3];

      for(auto bid: prev_beam_ids){
        auto& state = pool[bid];
        idx.emplace_back(-state.cookie, bid);
      }

      sort(idx.begin(), idx.end());

      auto& best_state = pool[idx.front().second];

      vector<pair<Command, Facility>> res;
      // shared_ptr<Movement> last_move = best_state.movement;
      Movement* last_move = &(movement_pool.pool[best_state.movement]);
      while(true){
        res.emplace_back(last_move -> cmd, last_move -> target);
        if(last_move -> turn == 0) break;
        // last_move = last_move -> prev;
        last_move = &(movement_pool.pool[last_move -> prev]);
      }

      // assert((int)res.size() == n);

      eprintln("Beam Search completd :", timer::get()*1000, "[ms]");
      eprintln("score = ", best_state.cookie * 1e-9);

      reverse(res.begin(), res.end());

      return res;
    }
  }

  vector<pair<Command, Facility>> dp(const vector<pair<Command, Facility>>& last){
    vector<pair<Command, Facility>> cmd;
    for(int i=0; i<(int)last.size(); i++){
      if(last[i].first != Command::CLICK){
        if(last[i].first != Command::SELL){
          cmd.emplace_back(last[i]);
        }
      }
    }

    struct cmd_state{
      Int click_prod;
      Int cookie_prod_per_turn;
      Int pay;
      array<int, num_facilities> facility_cnt{};
      array<int, num_facilities> facility_level{};
    };

    vector<cmd_state> c;
    c.emplace_back(cmd_state{
      1,
      0,
      0,
      {1, 0, 0, 0, 0, 0},
      {}
    });
    for(int i=0; i<(int)cmd.size(); i++){
      auto tmp = c.back();
      if(cmd[i].first == Command::BUY){
        tmp.cookie_prod_per_turn += get_prod(cmd[i].second, tmp.facility_level[(int)cmd[i].second]);
        tmp.pay = get_buy_price(cmd[i].second, tmp.facility_cnt[(int)cmd[i].second]);
        tmp.facility_cnt[(int)cmd[i].second]++;
      }else if(cmd[i].first == Command::REINFORCE){
        if(cmd[i].second == Facility::CLICK){
          tmp.click_prod = get_prod(cmd[i].second, tmp.facility_level[(int)cmd[i].second] + 1);
        }else{
          Int diff = get_prod(cmd[i].second, tmp.facility_level[(int)cmd[i].second] + 1) -
            get_prod(cmd[i].second, tmp.facility_level[(int)cmd[i].second]);
          tmp.cookie_prod_per_turn += tmp.facility_cnt[(int)cmd[i].second] * diff;
        }
        tmp.pay = get_enh_price(cmd[i].second, tmp.facility_level[(int)cmd[i].second]);
        tmp.facility_level[(int)cmd[i].second]++;
      }
      c.emplace_back(tmp);
    }

    movement_pool.init();
    
    // using st = tuple<Int, int, int>; // (cookies, level, prev movement)
    struct st{
      Int cookies;
      int level;
      int prev;
      st():cookies(0), level(0), prev(-1){}
      st(Int a, int b, int c):cookies(a), level(b), prev(c){}
    };

    vector<st> state_stack;
    state_stack.emplace_back();
    for(int i=0; i<n; i++){
      // eprintln(state_stack.size());
      vector<st> next_state_stack;
      for(int j=0; j<(int)state_stack.size(); j++){
        Int cookies = state_stack[j].cookies;
        int command_level = state_stack[j].level;
        int prev = state_stack[j].prev;

        { // click
          Int gain = c[command_level].click_prod + c[command_level].cookie_prod_per_turn;
          if(fever[i]){
            gain *= 7;
          }
          Int next_cookies = cookies + gain;
          if(s[i+1] == 'B'){
            next_cookies = (next_cookies * 101 + 99) / 100;
          }

          while(next_state_stack.size() && next_state_stack.back().cookies <= next_cookies){
            if(next_state_stack.back().prev != -1) movement_pool.erase(next_state_stack.back().prev);
            next_state_stack.pop_back();
          }

          if(next_state_stack.size() == 0 || next_state_stack.back().level != command_level){
            int mv = movement_pool.set(Movement{
              i,
              Command::CLICK,
              Facility::NONE,
              prev
            });

            next_state_stack.emplace_back(next_cookies, command_level, mv);
          }
        }
        if(command_level+1 < (int)c.size()){ // next command
          command_level++;
          Int pay = c[command_level].pay;
          if(s[i] == 'S'){
            pay = (pay * 90 + 99) / 100;
          }

          Int next_cookies = cookies - pay;
          if(next_cookies < 0) continue;

          Int gain = c[command_level].cookie_prod_per_turn;
          if(fever[i]){
            gain *= 7;
          }

          next_cookies += gain;

          if(s[i+1] == 'B'){
            next_cookies = (next_cookies * 101 + 99) / 100;
          }

          while(next_state_stack.size() && next_state_stack.back().cookies <= next_cookies){
            if(next_state_stack.back().prev != -1) movement_pool.erase(next_state_stack.back().prev);
            next_state_stack.pop_back();
          }

          if(next_state_stack.size() == 0 || next_state_stack.back().level != command_level){
            int mv = movement_pool.set(Movement{
              i,
              cmd[command_level-1].first,
              cmd[command_level-1].second,
              prev
            });

            next_state_stack.emplace_back(next_cookies, command_level, mv);
          }
        }
      }

      swap(state_stack, next_state_stack);
    }

    // restore
    vector<pair<Command, Facility>> res;
    int prev = -1;
    {
      Movement* last_move = &(movement_pool.pool[state_stack.front().prev]);
      while(true){
        res.emplace_back(last_move -> cmd, last_move -> target);
        if(last_move -> turn == 0) break;
        Movement* prev_move = &(movement_pool.pool[last_move -> prev]);
        if(prev == -1 && prev_move -> cmd != Command::CLICK){
          prev = last_move -> prev;
        }
        last_move = prev_move;
      }

      assert((int)res.size() == n);

      eprintln("DP completd :", timer::get()*1000, "[ms]");
      eprintln("score = ", state_stack.front().cookies * 1e-9);

      reverse(res.begin(), res.end());
    }

    while(res.size() && res.back().first == Command::CLICK){
      res.pop_back();
    }

    State dp_result{
      calc_score(res),
      c.back().cookie_prod_per_turn,
      0,
      c.back().facility_cnt,
      c.back().facility_level,
      prev,
      0
    };

    return beam_search(dp_result, res.size());
  }

  Int calc_score(const vector<pair<Command, Facility>>& res){
    Int cookies = 0;
    Int click_gain = 1;
    Int cookie_prod_per_turn = 0;

    vector<int> f_level(num_facilities, 0);
    vector<int> f_cnt(num_facilities, 0);

    assert((int)res.size() <= n);

    for(int i=0; i<min<int>(res.size(), n); i++){
      if(res[i].first == Command::BUY){
        Int pay = get_buy_price(res[i].second, f_cnt[(int)res[i].second]);
        if(s[i] == 'S'){
          pay = (pay * 90 + 99) / 100;
        }
        cookies -= pay;
        cookie_prod_per_turn += get_prod(res[i].second, f_level[(int)res[i].second]);
        f_cnt[(int)res[i].second]++;
      }else if(res[i].first == Command::REINFORCE){
        Int pay = get_enh_price(res[i].second, f_level[(int)res[i].second]);
        if(s[i] == 'S'){
          pay = (pay * 90 + 99) / 100;
        }
        cookies -= pay;
        Int diff = get_prod(res[i].second, f_level[(int)res[i].second]+1) - get_prod(res[i].second, f_level[(int)res[i].second]);
        if(res[i].second == Facility::CLICK){
          click_gain = get_prod(res[i].second, f_level[(int)res[i].second]+1) ;
        }else{
          cookie_prod_per_turn += diff * f_cnt[(int)res[i].second];
        }
        f_level[(int)res[i].second]++;
      }else if(res[i].first == Command::SELL){
        Int gain = get_buy_price(res[i].second, f_cnt[(int)res[i].second] - 1);
        gain = (gain * 25 + 99) / 100;
        cookies += gain;
        cookie_prod_per_turn -= get_prod(res[i].second, f_level[(int)res[i].second]);
        f_cnt[(int)res[i].second]--;
      }else if(res[i].first == Command::CLICK){
        Int gain = click_gain;
        if(fever[i]){
          gain *= 7;
        }
        cookies += gain;
      }

      Int gain = cookie_prod_per_turn;
      if(fever[i]) gain *= 7;
      cookies += gain;

      if(s[i+1] == 'B'){
        cookies = (cookies * 101 + 99) / 100;
      }
    }

    return cookies;
  }

  void output(const vector<pair<Command, Facility>>& res){
    for(int i=0; i<n; i++){
      #ifndef LOCAL_TEST
        println(get_command_str(res[i].first, res[i].second));
        string response;
        cin >> response;
        assert(response == "ok"s);
        // assert(response != "-1"s);
      #else
        if(res[i].first != Command::CLICK){
          println("turn =", i, ", cmd = ", get_command_str(res[i].first, res[i].second));
        }
      #endif
    }

    Int cookies = calc_score(res);
    eprintln("score =", cookies * 1e-9);
  }
};

int main(int argc, char* argv[]){
  timer::init();
  for(int i=1; i+1<argc; i++){
    if(argv[i] == "-ww"s){
      ww = stod(string(argv[++i]));
    }
  }
  Solver sol(cin);
  sol.solve();

  // for(int i=0; i<num_facilities; i++){
  //   eprintln(facility_name[i]);
  //   eprintln("buy price:", buy_price[i]);
  //   eprintln("enh price:", enh_price[i]);
  //   eprintln("enh price:", prod[i]);
  // }

  return 0;
}
0