第14回日本情報オリンピック 本選1：鉄道旅行 (Railroad Trip)

問題

https://joi2015ho.contest.atcoder.jp/tasks/joi2015ho_a

制約

  • 2 \le n \le 10^5
  • 2 \le m \le 10^5
  • 1 \le b_i \lt a_i \le 10^5
  • 1 \le c \le 10^5

考え方

ある鉄道の区間 [i, i+1] を何回か通ることになる。そのたびにコストがかかるので鉄道 i を通る回数を k_i とすると、

\displaystyle \sum min(k_i \times a_i, k_i \times b_i + c_i)

で求めることができる。各鉄道の通る区間の回数は [p_i, p_{i+1}) の区間に +1 される。連続区間に同じ数を和するのは imos法で実現することができるので、各鉄道を通る回数 k_i を求めることができた。

Submission #3785794 - 第１４回日本情報オリンピック 本選（オンライン）

どこに着目して考察するべきだったか

連続区間に同じ数を足したい -> imos法

何がバグっていたか

得た知見

類題