結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2018-12-05 05:37:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 7,256 ms / 10,000 ms |
| コード長 | 27,910 bytes |
| コンパイル時間 | 2,830 ms |
| 実行使用メモリ | 100,912 KB |
| スコア | 278,712,224,304 |
| 平均クエリ数 | 10000.00 |
| 最終ジャッジ日時 | 2021-07-19 08:44:21 |
| 合計ジャッジ時間 | 221,702 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 5,963 ms
97,888 KB |
| testcase_01 | AC | 6,217 ms
97,672 KB |
| testcase_02 | AC | 6,649 ms
97,732 KB |
| testcase_03 | AC | 5,946 ms
98,252 KB |
| testcase_04 | AC | 6,613 ms
99,312 KB |
| testcase_05 | AC | 6,156 ms
98,356 KB |
| testcase_06 | AC | 6,993 ms
98,576 KB |
| testcase_07 | AC | 6,565 ms
98,612 KB |
| testcase_08 | AC | 7,256 ms
98,604 KB |
| testcase_09 | AC | 6,198 ms
98,176 KB |
| testcase_10 | AC | 6,422 ms
98,532 KB |
| testcase_11 | AC | 6,982 ms
98,416 KB |
| testcase_12 | AC | 5,951 ms
97,404 KB |
| testcase_13 | AC | 6,071 ms
97,852 KB |
| testcase_14 | AC | 5,971 ms
97,364 KB |
| testcase_15 | AC | 6,337 ms
98,120 KB |
| testcase_16 | AC | 6,128 ms
97,884 KB |
| testcase_17 | AC | 5,958 ms
98,020 KB |
| testcase_18 | AC | 6,353 ms
97,988 KB |
| testcase_19 | AC | 6,066 ms
98,264 KB |
| testcase_20 | AC | 6,548 ms
98,768 KB |
| testcase_21 | AC | 6,259 ms
98,380 KB |
| testcase_22 | AC | 6,644 ms
98,124 KB |
| testcase_23 | AC | 6,715 ms
98,520 KB |
| testcase_24 | AC | 6,197 ms
98,096 KB |
| testcase_25 | AC | 5,920 ms
97,632 KB |
| testcase_26 | AC | 6,763 ms
98,252 KB |
| testcase_27 | AC | 6,183 ms
97,372 KB |
| testcase_28 | AC | 5,669 ms
98,016 KB |
| testcase_29 | AC | 5,778 ms
98,096 KB |
| testcase_30 | AC | 6,494 ms
98,088 KB |
| testcase_31 | AC | 6,666 ms
98,084 KB |
ソースコード
#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 = 400;
// 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;
}