/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は N 人のメンバーからなるグループのリーダーです。メンバーには 1 から N までの番号が付けられており、メンバー i (1 \le i \le N) の実力値は A_i です。
高橋君は、このグループを連続する番号の境界で二つのチームに分けようとしています。具体的には、ある整数 k (1 \le k < N) を選び、メンバー 1 からメンバー k までを「チーム A」、メンバー k+1 からメンバー N までを「チーム B」とします。
このとき、チーム A の実力値の総和を S_1 = A_1 + A_2 + \cdots + A_k 、チーム B の実力値の総和を S_2 = A_{k+1} + A_{k+2} + \cdots + A_N とします。
k を最適に選んだときの |S_1 - S_2| の最小値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N A_1 A_2 \cdots A_N
- 1 行目には、メンバーの人数を表す整数 N が与えられる。
- 2 行目には、メンバー 1 からメンバー N までの実力値を表す N 個の整数 A_1, A_2, \ldots, A_N が空白区切りで与えられる。
出力
|S_1 - S_2| の最小値を 1 行に出力してください。
入力例 1
4 1 2 3 4
出力例 1
2
入力例 2
5 1 3 2 2 4
出力例 2
0
入力例 3
15 8 1 6 3 5 7 4 9 2 10 12 11 14 13 15
出力例 3
10
入力例 4
40 17 23 5 11 29 31 7 13 19 2 37 41 3 43 47 53 59 61 67 71 73 79 83 89 97 101 107 109 113 127 131 137 139 149 151 157 163 167 173 179
出力例 4
71
入力例 5
2 1000000000 1000000000
出力例 5
0
Score : 300 pts
Problem Statement
Takahashi is the leader of a group consisting of N members. The members are numbered from 1 to N, and the skill value of member i (1 \le i \le N) is A_i.
Takahashi wants to divide this group into two teams at a boundary of consecutive numbers. Specifically, he chooses an integer k (1 \le k < N), and assigns members 1 through k to "Team A" and members k+1 through N to "Team B".
Let the sum of skill values of Team A be S_1 = A_1 + A_2 + \cdots + A_k, and the sum of skill values of Team B be S_2 = A_{k+1} + A_{k+2} + \cdots + A_N.
Find the minimum value of |S_1 - S_2| when k is chosen optimally.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N A_1 A_2 \cdots A_N
- The first line contains an integer N representing the number of members.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the skill values of members 1 through N.
Output
Print the minimum value of |S_1 - S_2| on a single line.
Sample Input 1
4 1 2 3 4
Sample Output 1
2
Sample Input 2
5 1 3 2 2 4
Sample Output 2
0
Sample Input 3
15 8 1 6 3 5 7 4 9 2 10 12 11 14 13 15
Sample Output 3
10
Sample Input 4
40 17 23 5 11 29 31 7 13 19 2 37 41 3 43 47 53 59 61 67 71 73 79 83 89 97 101 107 109 113 127 131 137 139 149 151 157 163 167 173 179
Sample Output 4
71
Sample Input 5
2 1000000000 1000000000
Sample Output 5
0