B. Lecture Sleep

Codeforces

IDCF961B

Time1000ms

Memory256MB

Difficulty—

data structuresdpimplementationtwo pointers

English · Original

Chinese · Translation

Formal · Original

Your friend Mishka and you attend a calculus lecture. Lecture lasts _n_ minutes. Lecturer tells _a__i_ theorems during the _i_\-th minute. Mishka is really interested in calculus, though it is so hard to stay awake for all the time of lecture. You are given an array _t_ of Mishka's behavior. If Mishka is asleep during the _i_\-th minute of the lecture then _t__i_ will be equal to 0, otherwise it will be equal to 1. When Mishka is awake he writes down all the theorems he is being told — _a__i_ during the _i_\-th minute. Otherwise he writes nothing. You know some secret technique to keep Mishka awake for _k_ minutes straight. However you can use it **only once**. You can start using it at the beginning of any minute between 1 and _n_ - _k_ + 1. If you use it on some minute _i_ then Mishka will be awake during minutes _j_ such that and will write down all the theorems lecturer tells. You task is to calculate the maximum number of theorems Mishka will be able to write down if you use your technique **only once** to wake him up. ## Input The first line of the input contains two integer numbers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 105) — the duration of the lecture in minutes and the number of minutes you can keep Mishka awake. The second line of the input contains _n_ integer numbers _a_1, _a_2, ... _a__n_ (1 ≤ _a__i_ ≤ 104) — the number of theorems lecturer tells during the _i_\-th minute. The third line of the input contains _n_ integer numbers _t_1, _t_2, ... _t__n_ (0 ≤ _t__i_ ≤ 1) — type of Mishka's behavior at the _i_\-th minute of the lecture. ## Output Print only one integer — the maximum number of theorems Mishka will be able to write down if you use your technique **only once** to wake him up. [samples] ## Note In the sample case the better way is to use the secret technique at the beginning of the third minute. Then the number of theorems Mishka will be able to write down will be equal to 16.

你的朋友 Mishka 和你一起参加微积分讲座。讲座持续 #cf_span[n] 分钟。在第 #cf_span[i] 分钟，讲师讲解了 #cf_span[ai] 个定理。 Mishka 对微积分非常感兴趣，但他很难在整个讲座过程中保持清醒。给你一个数组 #cf_span[t] 表示 Mishka 的行为。如果在第 #cf_span[i] 分钟 Mishka 处于睡眠状态，则 #cf_span[ti] 等于 #cf_span[0]；否则等于 #cf_span[1]。当 Mishka 醒着时，他会记下讲师讲解的所有定理——即在第 #cf_span[i] 分钟记下 #cf_span[ai] 个定理；否则他什么也不写。你知道一种秘密技巧，可以连续保持 Mishka 醒着 #cf_span[k] 分钟。但你只能使用一次。你可以在第 #cf_span[1] 到第 #cf_span[n - k + 1] 分钟的任意一分钟开始使用该技巧。如果你在第 #cf_span[i] 分钟使用它，则 Mishka 将在满足的所有分钟 #cf_span[j] 中保持清醒，并记下讲师在这些分钟讲解的所有定理。你的任务是计算：如果你仅使用一次该技巧唤醒 Mishka，他最多能记下多少个定理。输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n ≤ 105]) —— 讲座的持续时间（分钟）和你能保持 Mishka 醒着的分钟数。输入的第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... an] (#cf_span[1 ≤ ai ≤ 104]) —— 讲师在第 #cf_span[i] 分钟讲解的定理数量。输入的第三行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ... tn] (#cf_span[0 ≤ ti ≤ 1]) —— Mishka 在第 #cf_span[i] 分钟的行为类型。仅输出一个整数：如果你仅使用一次该技巧唤醒 Mishka，他最多能记下的定理数量。在样例中，更好的做法是在第三分钟开始使用秘密技巧。此时 Mishka 能记下的定理数量为 #cf_span[16]。 ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n ≤ 105]) —— 讲座的持续时间（分钟）和你能保持 Mishka 醒着的分钟数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... an] (#cf_span[1 ≤ ai ≤ 104]) —— 讲师在第 #cf_span[i] 分钟讲解的定理数量。第三行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ... tn] (#cf_span[0 ≤ ti ≤ 1]) —— Mishka 在第 #cf_span[i] 分钟的行为类型。 ## Output 仅输出一个整数：如果你仅使用一次该技巧唤醒 Mishka，他最多能记下的定理数量。 [samples] ## Note 在样例中，更好的做法是在第三分钟开始使用秘密技巧。此时 Mishka 能记下的定理数量为 #cf_span[16]。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 10^5 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of theorems told in minute $ i $. Let $ T = (t_1, t_2, \dots, t_n) $ be a binary sequence, where $ t_i = 1 $ if Mishka is awake in minute $ i $, and $ t_i = 0 $ if asleep. **Constraints** 1. $ 1 \leq a_i \leq 10^4 $ for all $ i \in \{1, \dots, n\} $ 2. $ t_i \in \{0, 1\} $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq k \leq n $ **Objective** Let $ S_{\text{base}} = \sum_{i=1}^n t_i a_i $ be the number of theorems Mishka writes down without intervention. For any starting minute $ i \in \{1, \dots, n - k + 1\} $, applying the technique makes Mishka awake during minutes $ i, i+1, \dots, i+k-1 $. The additional theorems gained by applying the technique starting at $ i $ is: $$ \Delta_i = \sum_{j=i}^{i+k-1} (1 - t_j) a_j $$ This is the sum of theorems in the interval $ [i, i+k-1] $ that Mishka would have missed while asleep. The total theorems written with technique applied at $ i $ is: $$ S_i = S_{\text{base}} + \Delta_i $$ **Goal**: Compute $$ \max_{i=1}^{n - k + 1} S_i = S_{\text{base}} + \max_{i=1}^{n - k + 1} \sum_{j=i}^{i+k-1} (1 - t_j) a_j $$

Samples

Input #1

6 3
1 3 5 2 5 4
1 1 0 1 0 0

Output #1

API Response (JSON)

{
  "problem": {
    "name": "B. Lecture Sleep",
    "description": {
      "content": "Your friend Mishka and you attend a calculus lecture. Lecture lasts _n_ minutes. Lecturer tells _a__i_ theorems during the _i_\\-th minute. Mishka is really interested in calculus, though it is so har",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF961B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your friend Mishka and you attend a calculus lecture. Lecture lasts _n_ minutes. Lecturer tells _a__i_ theorems during the _i_\\-th minute.\n\nMishka is really interested in calculus, though it is so har...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你的朋友 Mishka 和你一起参加微积分讲座。讲座持续 #cf_span[n] 分钟。在第 #cf_span[i] 分钟，讲师讲解了 #cf_span[ai] 个定理。\n\nMishka 对微积分非常感兴趣，但他很难在整个讲座过程中保持清醒。给你一个数组 #cf_span[t] 表示 Mishka 的行为。如果在第 #cf_span[i] 分钟 Mishka 处于睡眠状态，则 #cf_span[t...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 10^5 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of theorems tol...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments