ABC076 D AtCoder Express
小数きらい
問題概要
次のような列車を運行する。
- 走行開始時と走行終了時には列車は止まっていなければならない。
- 列車の走行時間は
秒である。
- 最初の
秒間は列車は速度
以内で走行しなければならない。また次の
秒間は列車は速度
以内で走行しなければならない。次の
秒間、またそれ以降も同様である。
- 最後の
秒間は列車は速度
以内で走行しなければならない。
- 列車の性能上、加速度は
以内でなければならない。
このとき、列車が発車してから停車するまでに走れる最大の距離を求める。
制約
解法
- 累積和をとって、発車時刻を0としたときの各区間の最初の時刻と最後の時刻を求めておく
- 各時刻における最大速度を計算する（速度が大きいほど走行距離が長くなるので）
- 総和を計算して出力する
各時刻における最大速度を計算するのが面倒で、
- 「速度は
ずつしか増やせないけど、速度を落とすのは一瞬」というルールでの各時刻における最大速度
- 「速度を落とすのは
を計算し、minをとればよい。
また、入力例4からわかるとおり、1秒きざみではうまくいかないので、最大速度を0.5秒きざみで考える必要がある。
