Balance [AtCoder Beginner Contest 129 B]

https://atcoder.jp/contests/abc129/tasks/abc129_b

解説

https://atcoder.jp/contests/abc129/submissions/5859689

グループの分け方はN-1通りあるので、それを全探索して、差の絶対値の最小値を求める。
2つのグループに分けたあと、それぞれの重さの和を求めるには累積和を使うと最適。
しかし、使わなくても計算量的には問題ない。
一応累積和解法を紹介しておく。
　
W[i] := 番号iの重りの重さ
であるが、W[i] += W[i - 1]という計算を繰り返すことで、
W[i] := 番号i以下の重りの重さ
というふうに変換できる。
そうすると、
T以下のものの重さはs1 = W[T]であり、
Tより大きいものの重さはs2 = W[N-1]-W[T]となる。
あとは、差の最小値を求めて答える。

int N, W[101];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> W[i];
	rep(i, 1, N) W[i] += W[i - 1];

	int ans = inf;
	rep(T, 0, N - 1) {
		int s1 = W[T];
		int s2 = W[N - 1] - s1;
		chmin(ans, abs(s1 - s2));
	}

	cout << ans << endl;
}