AtCoder Regular Contest 100 : D - Equal Cut

問題

長さ N の整数列 A を４つの連続する部分列に分けたとき、４つの数列のそれぞれの和の最大値と最小値の差を最小化すると差はどうなるか、という問題。

解法

４つに分けるので半分の半分だと考える。最初に半分に切るところは全通り試すとして、分けて残った２つをどう分けるかと考える。(残った２つそれぞれの和) / 2 に近くして分けられればいいと思うので std::lower_bound() を使って分けるところを（「(残った２つそれぞれの和) / 2」を超える最初の要素か、その前かの）２つ試す。あとはコーナーケースとなるケースは別に処理を書いてあげれば OK。inf が十分大きくなかったみたいで WA を連発した。600 点問題にしては解法が単純な気がした。