B. Japanese Crosswords Strike Back

Codeforces

IDCF884B

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

A one-dimensional Japanese crossword can be represented as a binary string of length _x_. An encoding of this crossword is an array _a_ of size _n_, where _n_ is the number of segments formed completely of 1's, and _a__i_ is the length of _i_\-th segment. No two segments touch or intersect. For example: * If _x_ = 6 and the crossword is 111011, then its encoding is an array {3, 2}; * If _x_ = 8 and the crossword is 01101010, then its encoding is an array {2, 1, 1}; * If _x_ = 5 and the crossword is 11111, then its encoding is an array {5}; * If _x_ = 5 and the crossword is 00000, then its encoding is an empty array. Mishka wants to create a new one-dimensional Japanese crossword. He has already picked the length and the encoding for this crossword. And now he needs to check if there is **exactly one** crossword such that its length and encoding are equal to the length and encoding he picked. Help him to check it! ## Input The first line contains two integer numbers _n_ and _x_ (1 ≤ _n_ ≤ 100000, 1 ≤ _x_ ≤ 109) — the number of elements in the encoding and the length of the crossword Mishka picked. The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 10000) — the encoding. ## Output Print _YES_ if there exists **exaclty one** crossword with chosen length and encoding. Otherwise, print _NO_. [samples]

一维日本填字游戏可以用一个长度为 $x$ 的二进制字符串表示。该填字游戏的编码是一个长度为 $n$ 的数组 $a$，其中 $n$ 是由全 $1$ 组成的连续段的数量，而 $a_i$ 是第 $i$ 个段的长度。任意两个段都不相邻或相交。例如： Mishka 想要创建一个新的二维日本填字游戏。他已经确定了该填字游戏的长度和编码。现在他需要检查是否存在 *恰好一个* 填字游戏，其长度和编码与他选定的完全一致。请帮助他验证！第一行包含两个整数 $n$ 和 $x$（$1 ≤ n ≤ 100000$，$1 ≤ x ≤ 10^9$）——编码中元素的个数以及 Mishka 选定的填字游戏长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 ≤ a_i ≤ 10000$）——编码。如果存在 *恰好一个* 满足所选长度和编码的填字游戏，请输出 _YES_；否则输出 _NO_。 ## Input 第一行包含两个整数 $n$ 和 $x$（$1 ≤ n ≤ 100000$，$1 ≤ x ≤ 10^9$）——编码中元素的个数以及 Mishka 选定的填字游戏长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 ≤ a_i ≤ 10000$）——编码。 ## Output 如果存在 *恰好一个* 满足所选长度和编码的填字游戏，请输出 _YES_；否则输出 _NO_。 [samples]

**Input Data** * $n, x \in \mathbb{Z}$ such that $1 \le n \le 10^5$ and $1 \le x \le 10^9$. * A sequence $A = (a_1, a_2, \dots, a_n)$ where $a_i \in \mathbb{Z}$ and $1 \le a_i \le 10^4$ for all $1 \le i \le n$. **Definitions** Let $\mathcal{S}$ be the set of valid segment starting positions $P = (p_1, p_2, \dots, p_n) \in \mathbb{Z}^n$ satisfying the following system of inequalities: 1. $p_1 \ge 1$ 2. $p_{i+1} \ge p_i + a_i + 1, \quad \forall i \in \{1, \dots, n-1\}$ 3. $p_n + a_n - 1 \le x$ **Objective** Determine the cardinality $|\mathcal{S}|$. **Output** $$ \text{Output} = \begin{cases} \text{YES} & \text{if } |\mathcal{S}| = 1 \\ \text{NO} & \text{otherwise} \end{cases} $$

Samples

Input #1

2 4
1 3

Output #1

NO

Input #2

3 10
3 3 2

Output #2

YES

Input #3

2 10
1 3

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "B. Japanese Crosswords Strike Back",
    "description": {
      "content": "A one-dimensional Japanese crossword can be represented as a binary string of length _x_. An encoding of this crossword is an array _a_ of size _n_, where _n_ is the number of segments formed complete",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF884B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A one-dimensional Japanese crossword can be represented as a binary string of length _x_. An encoding of this crossword is an array _a_ of size _n_, where _n_ is the number of segments formed complete...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一维日本填字游戏可以用一个长度为 $x$ 的二进制字符串表示。该填字游戏的编码是一个长度为 $n$ 的数组 $a$，其中 $n$ 是由全 $1$ 组成的连续段的数量，而 $a_i$ 是第 $i$ 个段的长度。任意两个段都不相邻或相交。\n\n例如：\n\nMishka 想要创建一个新的二维日本填字游戏。他已经确定了该填字游戏的长度和编码。现在他需要检查是否存在 *恰好一个* 填字游戏，其长度和编码与他选定...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Input Data**\n*   $n, x \\in \\mathbb{Z}$ such that $1 \\le n \\le 10^5$ and $1 \\le x \\le 10^9$.\n*   A sequence $A = (a_1, a_2, \\dots, a_n)$ where $a_i \\in \\mathbb{Z}$ and $1 \\le a_i \\le 10^4$ for all $1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments