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) }\]

となる.