ABC102 D - Equal Cut
問題概要
長さ N の整数列 A を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を P,Q,R,S とするとき、max(P,Q,R,S)−min(P,Q,R,S) の最小値を求めよ。
4≤N≤2×10の5乗
考えたこと
切れ目をそれぞれ入れていって、だんだんと最適解に近づかせるやり方で解こうとした。ちょっとACがあったので回答方針はあっていたように思える。難しい。
長さ N の整数列 A を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を P,Q,R,S とするとき、max(P,Q,R,S)−min(P,Q,R,S) の最小値を求めよ。
4≤N≤2×10の5乗
切れ目をそれぞれ入れていって、だんだんと最適解に近づかせるやり方で解こうとした。ちょっとACがあったので回答方針はあっていたように思える。難しい。