time limit per test 2 second memory limit per test 256 megabytes
Vasya has an array a consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).
Inserting an element in the same position he was erased from is also considered moving.
Can Vasya divide the array after choosing the right element to move and its new position?
The first line contains single integer n (1≤n≤100000) — the size of the array. The second line contains n integers a1,a2... an (1≤ai≤1e9) — the elements of the array.
Print YES if Vasya can divide the array after moving one element. Otherwise print NO.
因为只能移动一个数字 这题就很简单了 先记录一下前缀和 然后看每个位置的和 有三种情况 等于一半肯定可以 小于一半 那么肯定要从后面移一个数字过来 那么就看后面是否有sum/2-pre[i](前缀和) 大于一半 同理要看前面是否能往后移一个数字 就看前面是否含有pre[i](前缀和)-sum/2 这两个都可以分别用一个数组记录每个数出现在最左和最右的位置来实现总复杂度O(n) ## AC code:(不包含输入类)