/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたの今日の夕食はピザです。 1 から N の番号がついた N 個のピースが番号順に時計回りで並んでいます。 ピース N と 1 が隣り合っていることに注意してください。
ピース i の美味しさは a_i です。
あなたは連続したいくつかのピースを選んで食べます。 例えば 10 ピースのピザがあるとき、ピース 8,9,10,1,2 を選んで食べることはできますが、ピース 1,3,5 を選んで食べることはできません。
食べるピースの美味しさの総和を X、残るピースの美味しさの総和を Y として、|X-Y| としてありうる値の最小値を求めてください。
制約
- 与えられる入力は全て整数
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \cdots a_N
出力
食べるピースの美味しさの総和を X、残るピースの美味しさの総和を Y として、|X-Y| としてありうる値の最小値を出力せよ。
入力例 1
4 10 20 40 30
出力例 1
20
- ピース 4,1,2 を選んで食べるのが最適な選び方の 1 つです。
- このとき、食べるピースの美味しさの総和 X は 30+10+20=60、残るピースの美味しさの総和 Y は 40 で |X-Y| は 20 となります。
- ピース 1,3 やピース 2,4 は連続したいくつかのピースを選んでいないことに注意してください。
入力例 2
20 13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9
出力例 2
1
Score : 6 points
Warning
Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Your dinner today is a pizza. There are N pieces of the pizza, numbered 1 through N, arranged clockwise in this order. Note that Piece N and Piece 1 are adjacent to each other.
The deliciousness of Piece i is a_i.
You will choose some consecutive pieces and eat them. For example, if the pizza has 10 pieces, you can choose the pieces 8,9,10,1,2 and eat them, but cannot choose 1,3,5.
Find the minimum possible value of |X-Y| where X and Y are the sum of the deliciousness of the pieces you eat and that of the remaining pieces, respectively.
Constraints
- All values in input are integers.
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N a_1 \cdots a_N
Output
Print the minimum possible value of |X-Y| where X and Y are the sum of the deliciousness of the pieces you eat and that of the remaining pieces, respectively.
Sample Input 1
4 10 20 40 30
Sample Output 1
20
- One optimal choice is to choose to eat the pieces 4,1,2.
- Here, the sum of the deliciousness of the pieces you eat, X, is 30+10+20=60, and that of the remaining pieces, Y, is 40, resulting in |X-Y|=20.
- Note that neither choosing the pieces 1,3 nor choosing 2,4 is allowed since those sets of pieces are not consecutive.
Sample Input 2
20 13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9
Sample Output 2
1