D. Credit Card

Codeforces

IDCF893D

Time2000ms

Memory256MB

Difficulty—

data structuresdpgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

Recenlty Luba got a credit card and started to use it. Let's consider _n_ consecutive days Luba uses the card. **She starts with 0 money on her account.** In the **evening** of _i_\-th day a transaction _a__i_ occurs. If _a__i_ > 0, then _a__i_ bourles are deposited to Luba's account. If _a__i_ < 0, then _a__i_ bourles are withdrawn. And if _a__i_ = 0, then the amount of money on Luba's account is checked. In the **morning** of any of _n_ days Luba can go to the bank and deposit any **positive** integer amount of burles to her account. But there is a limitation: the amount of money on the account can never exceed _d_. **It can happen that the amount of money goes greater than _d_ by some transaction in the evening. In this case answer will be «-1».** Luba must not exceed this limit, and also she wants that **every day her account is checked** (the days when _a__i_ = 0) the amount of money on her account is non-negative. It takes a lot of time to go to the bank, so Luba wants to know the minimum number of days she needs to deposit some money to her account (if it is possible to meet all the requirements). Help her! ## Input The first line contains two integers _n_, _d_ (1 ≤ _n_ ≤ 105, 1 ≤ _d_ ≤ 109) —the number of days and the money limitation. The second line contains _n_ integer numbers _a_1, _a_2, ... _a__n_ ( - 104 ≤ _a__i_ ≤ 104), where _a__i_ represents the transaction in _i_\-th day. ## Output Print _\-1_ if Luba cannot deposit the money to her account in such a way that the requirements are met. Otherwise print the minimum number of days Luba has to deposit money. [samples]

最近，Luba 获得了一张信用卡并开始使用它。考虑 Luba 使用该卡的 #cf_span[n] 个连续天数。 *她在账户中初始有 #cf_span[0] 元钱。* 在第 #cf_span[i] 天的 *晚上*，发生一笔交易 #cf_span[ai]。如果 #cf_span[ai > 0]，则 #cf_span[ai] 卢布存入 Luba 的账户；如果 #cf_span[ai < 0]，则 #cf_span[ai] 卢布被取出；如果 #cf_span[ai = 0]，则检查 Luba 账户中的余额。在任意一天的 *早晨*，Luba 可以前往银行，向她的账户存入任意 *正整数* 数量的卢布。但有一个限制：账户中的金额绝不能超过 #cf_span[d]。 *如果某天晚上的交易导致账户余额超过 #cf_span[d]，则答案为 «-1»。* Luba 不能超过这个限额，并且她希望 *在每次账户被检查时*（即当 #cf_span[ai = 0] 的日子），账户余额均为非负数。去银行需要花费大量时间，因此 Luba 希望知道她最少需要在多少天存入资金（如果可以满足所有要求的话）。请帮助她！第一行包含两个整数 #cf_span[n], #cf_span[d] (#cf_span[1 ≤ n ≤ 105], #cf_span[1 ≤ d ≤ 109]) ——天数和金额限制。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... an] (#cf_span[ - 104 ≤ ai ≤ 104])，其中 #cf_span[ai] 表示第 #cf_span[i] 天的交易金额。如果 Luba 无法以满足要求的方式向账户存款，请输出 _-1_；否则输出 Luba 需要存款的最少天数。 ## Input 第一行包含两个整数 #cf_span[n], #cf_span[d] (#cf_span[1 ≤ n ≤ 105], #cf_span[1 ≤ d ≤ 109]) ——天数和金额限制。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... an] (#cf_span[ - 104 ≤ ai ≤ 104])，其中 #cf_span[ai] 表示第 #cf_span[i] 天的交易金额。 ## Output 如果 Luba 无法以满足要求的方式向账户存款，请输出 _-1_；否则输出 Luba 需要存款的最少天数。 [samples]

**Definitions** Let $ n, d \in \mathbb{Z}^+ $ be the number of days and the maximum allowed balance. Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the sequence of daily transactions, where $ a_i $ is the transaction on day $ i $. Let $ B_0 = 0 $ be the initial balance. For $ i \in \{1, \dots, n\} $, define the balance after the evening transaction on day $ i $ as: $$ B_i = B_{i-1} + a_i $$ Let $ C \subseteq \{1, \dots, n\} $ be the set of days where $ a_i = 0 $ (check days). **Constraints** 1. $ 1 \leq n \leq 10^5 $, $ 1 \leq d \leq 10^9 $ 2. $ -10^4 \leq a_i \leq 10^4 $ for all $ i $ 3. For all $ i \in \{1, \dots, n\} $: $ B_i \leq d $ 4. For all $ i \in C $: $ B_i \geq 0 $ 5. Luba may add any positive integer amount of money in the morning of any day, but only once per day. **Objective** Find the minimum number of days on which Luba must deposit money (in the morning) such that all constraints are satisfied. If impossible, output $-1$.

Samples

Input #1

5 10
-1 5 0 -5 3

Output #1

Input #2

3 4
-10 0 20

Output #2

\-1

Input #3

5 10
-5 0 10 -11 0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Credit Card",
    "description": {
      "content": "Recenlty Luba got a credit card and started to use it. Let's consider _n_ consecutive days Luba uses the card. **She starts with 0 money on her account.** In the **evening** of _i_\\-th day a transac",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF893D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Recenlty Luba got a credit card and started to use it. Let's consider _n_ consecutive days Luba uses the card.\n\n**She starts with 0 money on her account.**\n\nIn the **evening** of _i_\\-th day a transac...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "最近，Luba 获得了一张信用卡并开始使用它。考虑 Luba 使用该卡的 #cf_span[n] 个连续天数。\n\n*她在账户中初始有 #cf_span[0] 元钱。*\n\n在第 #cf_span[i] 天的 *晚上*，发生一笔交易 #cf_span[ai]。如果 #cf_span[ai > 0]，则 #cf_span[ai] 卢布存入 Luba 的账户；如果 #cf_span[ai < 0]，则 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, d \\in \\mathbb{Z}^+ $ be the number of days and the maximum allowed balance.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the sequence of daily transactions, wher...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments