ABC133 D - Rain Flows into Dams (400)
山1から片側に流れる量をXとして、他の山の値を次々求めていくと、
$ X = A_1 - A_2 + A_3 + \dots + A_n - X
となる
Xが上の式から求められるので、Aの値を使って他の山の値も次々と求められる
山1を求めるのが
$ O(N)
、その他の山を求めるのがそれぞれ
$ O(1)
なので、全体で
$ O(N)
問題:
https://atcoder.jp/contests/abc133/tasks/abc133_d
提出:
https://atcoder.jp/contests/abc133/submissions/6278233
#ABC133
#D
#400pt
#ABC
#AtCoder
#O(N)