ARC116 B - Products of Min-Max (400)
$ A
は昇順にソートしておく
$ N
が大きいので全パターンを確かめるのは間に合わない
自身がminになる時にmaxになる回数は自身が1回、右隣が1回、その右が2回、4回、8回と増えていく
列の右側から和を記憶しながら計算する
各要素毎に
これまでの和を2倍する
右隣の要素を和に加える
答えに和と自身の積と自身の2乗を加える
自身の2乗は要素数1の場合の計算
各要素毎に
$ O(1)
なので全体で
$ O(N)
問題:
https://atcoder.jp/contests/arc116/tasks/arc116_b
提出:
https://atcoder.jp/contests/arc116/submissions/21352540
#ARC116
#400pt
#B
#ARC
#AtCoder
#O(N)
#累積和