K. Easy vector

Codeforces

IDCF10073K

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You're given a vector with n elements. Piro starts from cell 1. He walks x seconds. In each second, he can move to an adjacent cell: for a cell i with 2 ≤ i ≤ n, he can move to i - 1 and i + 1. From cell 1 he can only move to cell 2 and from cell n he can only move to cell n-1. Initially, his sum is what's written on cell 1, from where he starts. Next x seconds, his sum increases by what's written on each cell he visits during those x seconds. What's the maximum sum he can get? Formally, given vector A, choose i1, i2, ..., ix such as you maximize the sum A[1] + A[i1] + A[i2] + ... + A[ix], where 1 ≤ ik ≤ n and |ik - ik - 1| = 1. Given an array and q queries, each query containing a value x, please answer all of them! The first line contains numbers n and q (1 ≤ n, q ≤ 105, n is at least 2). Next n lines contain the values of vector: each element of vector is between 1 and 105. Next q lines contain values of queries: each lines contains a new value for x (1 ≤ x ≤ 109). Output q lines, containing the answers for each query. ## Input The first line contains numbers n and q (1 ≤ n, q ≤ 105, n is at least 2). Next n lines contain the values of vector: each element of vector is between 1 and 105. Next q lines contain values of queries: each lines contains a new value for x (1 ≤ x ≤ 109). ## Output Output q lines, containing the answers for each query. [samples]

**Definitions** Let $ A, B, P \in \mathbb{Z}^+ $ be given constants, where: - $ A $ and $ B $ are fixed performance coefficients, - $ P $ is the minimum required performance in Performance Points. Let $ n \in \mathbb{Z}^+ $ denote the number of GPU cores. The performance function is: $$ P(n) = A \cdot n + B $$ **Constraints** 1. $ 1 \leq A \leq 10^5 $ 2. $ 1 \leq B \leq 10^5 $ 3. $ 1 \leq P \leq 10^9 $ **Objective** Find the minimal integer $ n $ such that: $$ A \cdot n + B \geq P $$

API Response (JSON)

{
  "problem": {
    "name": "K. Easy vector",
    "description": {
      "content": "You're given a vector with n elements. Piro starts from cell 1. He walks x seconds. In each second, he can move to an adjacent cell: for a cell i with 2 ≤ i ≤ n, he can move to i - 1 and i + 1. From c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10073K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given a vector with n elements. Piro starts from cell 1. He walks x seconds. In each second, he can move to an adjacent cell: for a cell i with 2 ≤ i ≤ n, he can move to i - 1 and i + 1. From c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A, B, P \\in \\mathbb{Z}^+ $ be given constants, where:  \n- $ A $ and $ B $ are fixed performance coefficients,  \n- $ P $ is the minimum required performance in Performance Point...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments