D. Array Division

Codeforces

IDCF808D

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresimplementation

English · Original

Chinese · Translation

Formal · Original

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? ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 100000) — the size of the array. The second line contains _n_ integers _a_1, _a_2... _a__n_ (1 ≤ _a__i_ ≤ 109) — the elements of the array. ## Output Print _YES_ if Vasya can divide the array after moving one element. Otherwise print _NO_. [samples] ## Note In the first example Vasya can move the second element to the end of the array. In the second example no move can make the division possible. In the third example Vasya can move the fourth element by one position to the left.

Vasya 有一个由正整数组成的数组 #cf_span[a]。Vasya 希望将这个数组划分为两个非空的连续部分（前缀和后缀），使得第一部分所有元素的和等于第二部分元素的和。但这种情况并不总是可能的，因此 Vasya 会在划分数组之前移动某个元素（Vasya 会删除某个元素，并将其插入到任意位置）。 *将元素插入到它被删除的相同位置也被视为移动。* Vasya 能否在选择正确的元素并确定其新位置后，将数组成功划分？第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——数组的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2... an]（#cf_span[1 ≤ ai ≤ 109]）——数组的元素。如果 Vasya 在移动一个元素后可以划分数组，则输出 _YES_；否则输出 _NO_。在第一个例子中，Vasya 可以将第二个元素移动到数组末尾。在第二个例子中，任何移动都无法使划分成为可能。在第三个例子中，Vasya 可以将第四个元素向左移动一个位置。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——数组的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2... an]（#cf_span[1 ≤ ai ≤ 109]）——数组的元素。 ## Output 如果 Vasya 在移动一个元素后可以划分数组，则输出 _YES_；否则输出 _NO_。 [samples] ## Note 在第一个例子中，Vasya 可以将第二个元素移动到数组末尾。在第二个例子中，任何移动都无法使划分成为可能。在第三个例子中，Vasya 可以将第四个元素向左移动一个位置。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the size of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers. **Constraints** $ 1 \leq n \leq 100000 $, $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $. **Objective** Determine whether there exists an index $ i \in \{1, \dots, n\} $ and a position $ j \in \{1, \dots, n\} $ (possibly $ j = i $) such that, after moving $ a_i $ from position $ i $ to position $ j $, the resulting array $ A' $ can be split into a non-empty prefix and a non-empty suffix with equal sums. That is, define $ A' $ as $ A $ with $ a_i $ relocated to index $ j $. Then, there exists $ k \in \{1, \dots, n-1\} $ such that: $$ \sum_{\ell=1}^{k} a'_\ell = \sum_{\ell=k+1}^{n} a'_\ell $$

Samples

Input #1

3
1 3 2

Output #1

YES

Input #2

5
1 2 3 4 5

Output #2

NO

Input #3

5
2 2 3 4 5

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "D. Array Division",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF808D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 有一个由正整数组成的数组 #cf_span[a]。Vasya 希望将这个数组划分为两个非空的连续部分（前缀和后缀），使得第一部分所有元素的和等于第二部分元素的和。但这种情况并不总是可能的，因此 Vasya 会在划分数组之前移动某个元素（Vasya 会删除某个元素，并将其插入到任意位置）。\n\n*将元素插入到它被删除的相同位置也被视为移动。*\n\nVasya 能否在选择正确的元素并确定其新位...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 100000 $, $ 1 \\leq ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments