Progressions Covering
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given two arrays: an array $a$ consisting of $n$ zeros and an array $b$ consisting of $n$ integers.
You can apply the following operation to the array $a$ an arbitrary number of times: choose some subsegment of $a$ of length $k$ and add the arithmetic progression $1, 2, \ldots, k$ to this subsegment — i. e. add $1$ to the first element of the subsegment, $2$ to the second element, and so on. The chosen subsegment should be inside the borders of the array $a$ (i.e., if the left border of the chosen subsegment is $l$, then the condition $1 \le l \le l + k - 1 \le n$ should be satisfied). Note that the progression added is always $1, 2, \ldots, k$ but not the $k, k - 1, \ldots, 1$ or anything else (i.e., the leftmost element of the subsegment always increases by $1$, the second element always increases by $2$ and so on).
Your task is to find the minimum possible number of operations required to satisfy the condition $a_i \ge b_i$ for each $i$ from $1$ to $n$. Note that the condition $a_i \ge b_i$ should be satisfied for all elements at once.
The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) — the number of elements in both arrays and the length of the subsegment, respectively.
The second line of the input contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^{12}$), where $b_i$ is the $i$-th element of the array $b$.
Print one integer — the minimum possible number of operations required to satisfy the condition $a_i \ge b_i$ for each $i$ from $1$ to $n$.
Input
The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) — the number of elements in both arrays and the length of the subsegment, respectively.
The second line of the input contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^{12}$), where $b_i$ is the $i$-th element of the array $b$.
Output
Print one integer — the minimum possible number of operations required to satisfy the condition $a_i \ge b_i$ for each $i$ from $1$ to $n$.
3 3
5 4 6
6 3
1 2 3 2 2 3
6 3
1 2 4 1 2 3
7 3
50 17 81 25 42 39 96
5
3
3
92
Note
Consider the first example. In this test, we don't really have any choice, so we need to add at least five progressions to make the first element equals $5$. The array $a$ becomes $[5, 10, 15]$.
Consider the second example. In this test, let's add one progression on the segment $[1; 3]$ and two progressions on the segment $[4; 6]$. Then, the array $a$ becomes $[1, 2, 3, 2, 4, 6]$.
CF Educational Codeforces Round 126
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 6
- Start at
- 2023-11-9 14:30
- End at
- 2023-11-9 17:00
- Duration
- 2.5 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 15