http://arc078.contest.atcoder.jp/tasks/arc078_a
解法
http://arc078.contest.atcoder.jp/submissions/1421601
カードの境界線を全探索すればよいのだが、すぬけくんとアライグマが取るカードの総和を求めているとTLEする。
累積和を使う方法もあるが、順番に境界線を探索するときは差分だけ更新する方法の方が簡単である。
x = [0,i]の総和
y = [i+1,N-1]の総和
であるとき、次のx,yは
x' = [0,i+1]の総和 = x + A[i + 1]
y' = [i+2,N-1]の総和 = y - A[i + 1]
であるため、これを順番にやっていき、abs(x - y)の最小値を答える。
#define INF 1LL<<60 typedef long long ll; int N, A[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; ll x = 0, y = 0; ll ans = INF; rep(i, 0, N) y += A[i]; rep(i, 0, N - 1) { x += A[i]; y -= A[i]; ans = min(ans, abs(x - y)); } cout << ans << endl; }