No.1645
\(C\) を \(B_i = -1\) となる \(i\) の集合とすると,
\[f(B) = \abs{ \sum_{i=1}^N A_i - 2 \sum_{i \in C} A_i }\]となる.
ここで, \(\sum_{i \in C} = X\) となる \(C\) の個数を数える. これは \(i\) 番目まで見たときに合計が \(j\) となる個数を \(D(i, j)\) とすると,
\[D(i, j) = D(i-1, j) + D(i-1, j-A_i)\]となるので, これを DP で計算する.
以上の計算結果を用いると,
\[\sum f(B) = \sum_X \abs { \sum_{i=1}^N A_i - 2 X D(N, X) }\]となる.