ABC258_D – Trophy

問題
提出
1. 解けた

問題

D - Trophy

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #44822739 - AtCoder Beginner Contest 258

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解けた

以下、解法を書く。

1度目のステージクリアには$A_i+B_i$時間がかかり、2度目のステージクリアには$B_i$時間がかかる。
X回ステージクリアするまでにあり得るパターンとしては、「Xまでのステージをクリアする」または「どこかのステージを複数回クリアする」になる。
$j$番目までの$A_i+B_i$の和を$ABS[j]$とする。
「Xまでのステージをクリアする」場合は単純に$ABS[X]$になる。
「どこかのステージを複数回クリアする」場合は、クリアする最大のステージを$T$として、$ABS[T]$と$Tまでの最小のB*(X-T)$となる。
複数回クリアするステージはTまでの最小の$B_i$が最適になる。