G. Good elements

Codeforces

IDCF10020G

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You are given a sequence A consisting of N integers. We will call the i-th element *good* if it equals the sum of some three elements in positions strictly smaller than i (an element can be used more than once in the sum). How many good elements does the sequence contain? The first line of input contains the positive integer N (1 ≤ N ≤ 5000), the length of the sequence A. The second line of input contains N space-separated integers representing the sequence A ( - 105 ≤ Ai ≤ 105). The first and only line of output must contain the number of good elements in the sequence. ## Input The first line of input contains the positive integer N (1 ≤ N ≤ 5000), the length of the sequence A.The second line of input contains N space-separated integers representing the sequence A ( - 105 ≤ Ai ≤ 105). ## Output The first and only line of output must contain the number of good elements in the sequence. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the length of the sequence. Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of integers, where $ a_i \in \mathbb{Z} $ for all $ i \in \{1, \dots, N\} $. **Constraints** 1. $ 1 \leq N \leq 5000 $ 2. $ -10^5 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, N\} $ **Objective** Define an element $ a_i $ (for $ i \geq 4 $) as *good* if there exist indices $ j, k, \ell \in \{1, \dots, i-1\} $ (not necessarily distinct) such that: $$ a_i = a_j + a_k + a_\ell $$ Compute the number of good elements in $ A $, i.e., $$ \left| \left\{ i \in \{4, \dots, N\} \mid \exists\, j,k,\ell \in \{1, \dots, i-1\} \text{ such that } a_i = a_j + a_k + a_\ell \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "G. Good elements",
    "description": {
      "content": "You are given a sequence A consisting of N integers. We will call the i-th element *good* if it equals the sum of some three elements in positions strictly smaller than i (an element can be used more ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10020G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a sequence A consisting of N integers. We will call the i-th element *good* if it equals the sum of some three elements in positions strictly smaller than i (an element can be used more ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the length of the sequence.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z} $ for all $ i \\in \\{1, \\dots, N\\}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments