新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
問題 
ベッシーは次のレースに備えて道を走ってトレーニングをしています。いかなる地形に対しても備えるためにこの道には上り坂も含まれています。彼女は直線のパスを考えて、それをなるべく速く走りたいと思っています。ただし彼女はM(1 ≤ M ≤ 10,000,000)秒以内に牧場に帰らなくてはいけません。
彼女が選んだ道は全部でT(1 ≤ T ≤ 100,000) 個のユニットからなり、ユニットは上り坂、平坦、下り坂があり、これらのユニットの長さは全て等しいとします。ベッシーは上り坂を1ユニット走るのにU(1 ≤ U ≤ 100)秒、平坦な道を1ユニット走るのにF(1 ≤ F ≤ 100)秒、下り坂を1ユニット走るのにD(1 ≤ D ≤ 100)秒かかります。牧場に戻る際には上り坂だったものが下り坂になり、下り坂だったものが上り坂になることに注意してください。
ベッシーが時間内に牧場に戻って来られるようにしつつ、最も遠く行くことのできる距離を求めてください。
入力
1行目 スペースで区切られた5つの整数: MとT,U,F,D
2~T+1行目 i+1行目は区間iのユニットを示す1文字: Si
出力
1行 ベッシーが時間内に牧場に戻って来られるようにしつつ、最も遠く行くことのできる距離
入力の例
13 5 3 2 1 u f u d f
出力の例
3
出典
USACO 2008 February Bronze
