Overview

This problem asks us to split an array into two halves at some single position and minimize the difference of the two partial sums \(|S_1 - S_2|\).
By trying all possible split positions while cleverly reusing the running sum, we can solve this efficiently.

Analysis

Let the split position be \(k\). Then:

• Team A’s sum: \(S_1 = A_1 + A_2 + \cdots + A_k\)
• Team B’s sum: \(S_2 = A_{k+1} + A_{k+2} + \cdots + A_N\)

We want to find the minimum value of \(|S_1 - S_2|\) over all \(1 \le k < N\).

Naive Approach

For each \(k\), if we:

• Compute the first half’s sum \(S_1\)
• Compute the second half’s sum \(S_2\)

then each \(k\) takes \(O(N)\) time.
Doing this for all \(k\) results in \(O(N^2)\) overall.

Since the constraint is \(N \le 2 \times 10^5\), \(O(N^2)\) is too slow.

---

Key Insight

If we precompute the total sum

\( \text{total} = A_1 + A_2 + \cdots + A_N \)

then once we know the first half’s sum \(S_1\), the second half’s sum \(S_2\) can be obtained instantly as

\( S_2 = \text{total} - S_1 \)

In other words, we move the split position one by one from left to right, and at each step:

• Add the next element to \(S_1\)
• Compute \(S_2 = \text{total} - S_1\)
• Update the minimum of the difference

---

Concrete Example

For example, when \(A = [1, 3, 2, 4]\), the total sum is

\( \text{total} = 1+3+2+4 = 10 \)

Going through each split position:

• \(k=1\)
  \(S_1=1\), \(S_2=9\)
  Difference is \(|1-9|=8\)

• \(k=2\)
  \(S_1=1+3=4\), \(S_2=6\)
  Difference is \(|4-6|=2\)

• \(k=3\)
  \(S_1=1+3+2=6\), \(S_2=4\)
  Difference is \(|6-4|=2\)

The minimum is \(2\).

As shown, we can examine all possible splits simply by incrementally increasing the first half’s sum.

Algorithm

1. Compute the total sum \(\text{total}\) of the entire array.
2. Start with \(S_1 = 0\).
3. Iterate from the left up to the \((N-1)\)-th element, and at each step:
   • \(S_1 += A_i\)
   • \(S_2 = \text{total} - S_1\)
   • Update the answer with \(|S_1 - S_2|\)
4. Output the minimum value at the end.

With this approach, we only need to look at each element once.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Since the split position \(k\) satisfies \(1 \le k < N\), it suffices to loop up to the \((n-1)\)-th element.

• In Python, integers are handled automatically regardless of size, so even large values like \(A_i \le 10^9\) pose no problem.

• In the code, we maintain s1 as the first half’s sum and total - s1 as the second half’s sum. This eliminates the need to recompute the second half’s sum from scratch each time.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:]
    
    total = sum(a)
    s1 = 0
    ans = float('inf')
    
    for i in range(n - 1):
        s1 += a[i]
        s2 = total - s1
        diff = abs(s1 - s2)
        if diff < ans:
            ans = diff
    
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.