A - 映画館
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 人の人が一列に並んだ M 個の座席に座っている。
i(1≦i≦N) 番目の人の座っている座席の両側ともに少なくとも A_i 個の空席が連続して存在することが分かっているとき、 M の最小値を求めよ。
N 人の人がこの順番で並んでいるとは限りません。(13:38)
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 .. A_N
- 一行目には人の数N(1≦N≦100000)が与えられる。
- 二行目には文章中で示された値 A_i(1≦A_i≦1000000000) が空白区切りで与えられる。
配点
この問題に部分点はありません。すべてのテストケースに正解すると100点です。
出力
座席数 M として考えられる最小値を答えよ。末尾に改行を入れること。
入力例1
3 2 3 2
出力例1
13
入力例2
5 6 6 9 7 4
出力例2
46
入力例3
10 10 6 6 10 3 8 8 9 4 2
出力例3
86