C: Splitting Pile - AtCoder Regular Contest 078

arc078.contest.atcoder.jp

数列a[i]が与えられる。|(a[1]+...+a[k]) - (a[k+1]+...+a[N])|を最小化せよ。

a[i]の累積和sum[i]を計算しておくと、(a[1]+...+a[k]) 及び (a[k+1]+...+a[N]) はそれぞれO(1)で計算可能。これでkを全探索すればよい。O(N)。