Codeforces Round 498(Div.3) C. Three Parts of the Array

Problem - C - Codeforces

問題概要

長さ の数列dが与えられる。
この数列dをA,B,Cの3つの連続する区間に分割する。（長さ0の区間が存在しても良い）

Aの長さをa、Aの要素の総和をsum1とする。
同様に、Bの長さをb、Bの要素の総和をsum2、Cの長さをc、Cの要素の総和をsum3とする。
なお、長さ0の区間の要素の総和は0とする。

sum1=sum3であるときのsum1の最大値を求めよ。

制約

解法

数列dの前からと後ろから累積和を取っておく。
sum3を大きい方から決め打ちして、sum3と等しくなるようなsum1があるか二分探索で求める。あればそれを出力して終了する。
計算量はO(N log N)

Submission #40442600 - Codeforces