初めに

atcoder.jp 解けなかったので

敗因

昨日解いた AGC020B みたいに, 各山について最小値 / 最大値がひとつ前から線形に求まるか...? みたいなことを考えていました. 実際は決まるのは最大値だけなのでそれは考えなくてもよいです. (よく考えると最大値しか知らないから最小値が出てくるわけがないがないですね...)

解法

条件を整理しましょう. $T$ をみると,

$\displaystyle \cdot \, H_i = T_i ( T_i \ne T_{i-1} ) \\ \cdot H_i \le T_i ( T_i = T_{i-1} )$

が成り立ちます. 同様に $B$ についても考えると, $\displaystyle \cdot \, H_i = T_i = A_i ( T_i \ne T_{i-1} \wedge A_i \ne A_{i+1} ) \\ \cdot H_i = T_i \le A_i ( T_i \ne T_{i-1} \wedge A_i = A_{i+1} ) \\ \cdot H_i \le T_i = A_i ( T_i = T_{i-1} \wedge A_i \ne A_{i+1} ) \\ \cdot H_i \le min(T_i, A_i) ( T_i = T_{i-1} \wedge A_i = A_{i+1} )$