English · Original
Chinese · Translation
Formal · Original
Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining side is occupied by a long wall that is split into _n_ sections. At this moment there are exactly _a__i_ archers located at the _i_\-th section of this wall. You know that archer who stands at section _i_ can shoot orcs that attack section located at distance not exceeding _r_, that is all such sections _j_ that |_i_ - _j_| ≤ _r_. In particular, _r_ = 0 means that archers are only capable of shooting at orcs who attack section _i_.
Denote as defense level of section _i_ the total number of archers who can shoot at the orcs attacking this section. Reliability of the defense plan is the minimum value of defense level of individual wall section.
There is a little time left till the attack so you can't redistribute archers that are already located at the wall. However, there is a reserve of _k_ archers that you can distribute among wall sections in arbitrary way. You would like to achieve maximum possible reliability of the defence plan.
## Input
The first line of the input contains three integers _n_, _r_ and _k_ (1 ≤ _n_ ≤ 500 000, 0 ≤ _r_ ≤ _n_, 0 ≤ _k_ ≤ 1018) — the number of sections of the wall, the maximum distance to other section archers can still shoot and the number of archers yet to be distributed along the wall. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 109) — the current number of archers at each section.
## Output
Print one integer — the maximum possible value of defense plan reliability, i.e. the maximum possible value of minimum defense level if we distribute _k_ additional archers optimally.
[samples]
今天你要带领一群精灵弓箭手保卫一座被愤怒的兽人军队攻击的城堡。城堡的三面被无法穿越的山脉保护，剩下的另一面是一堵长墙，被划分为 #cf_span[n] 个区段。目前，第 #cf_span[i] 个区段恰好有 #cf_span[ai] 名弓箭手。你知道，站在第 #cf_span[i] 区段的弓箭手可以射击攻击距离不超过 #cf_span[r] 的兽人，即所有满足 #cf_span[|i - j| ≤ r] 的区段 #cf_span[j]。特别地，#cf_span[r = 0] 表示弓箭手只能射击攻击第 #cf_span[i] 区段的兽人。
记第 #cf_span[i] 区段的 #cf_span(class=[tex-font-style-underline], body=[defense level]) 为能够射击攻击该区段的弓箭手总数。防御计划的 #cf_span(class=[tex-font-style-underline], body=[Reliability]) 定义为所有墙段防御等级的最小值。
攻击即将来临，你无法重新分配已位于墙上的弓箭手。然而，你还有 #cf_span[k] 名弓箭手作为后备力量，可以任意分配到各个墙段。你希望最大化防御计划的可靠性。
输入的第一行包含三个整数 #cf_span[n], #cf_span[r] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 500 000], #cf_span[0 ≤ r ≤ n], #cf_span[0 ≤ k ≤ 1018]) —— 墙段数量、弓箭手的最大射击距离以及待分配的弓箭手数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109]) —— 每个区段当前的弓箭手数量。
请输出一个整数 —— 防御计划可靠性的最大可能值，即在最优分配 #cf_span[k] 名额外弓箭手后，所有墙段防御等级的最小值的最大可能值。
## Input
输入的第一行包含三个整数 #cf_span[n], #cf_span[r] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 500 000], #cf_span[0 ≤ r ≤ n], #cf_span[0 ≤ k ≤ 1018]) —— 墙段数量、弓箭手的最大射击距离以及待分配的弓箭手数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109]) —— 每个区段当前的弓箭手数量。
## Output
请输出一个整数 —— 防御计划可靠性的最大可能值，即在最优分配 #cf_span[k] 名额外弓箭手后，所有墙段防御等级的最小值的最大可能值。
[samples]
**Definitions**
Let $ n, r, k \in \mathbb{Z} $, with $ 1 \leq n \leq 500{,}000 $, $ 0 \leq r \leq n $, $ 0 \leq k \leq 10^{18} $.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $ be the initial number of archers at each wall section.
Let $ x = (x_1, x_2, \dots, x_n) \in \mathbb{Z}_{\geq 0}^n $ be the vector of additional archers assigned to each section, such that $ \sum_{i=1}^n x_i \leq k $.
For each section $ i \in \{1, \dots, n\} $, define the **defense level** as:
$$
d_i(x) = \sum_{j = \max(1, i - r)}^{\min(n, i + r)} (a_j + x_j)
$$
The **reliability** of the defense plan is:
$$
R(x) = \min_{1 \leq i \leq n} d_i(x)
$$
**Constraints**
1. $ \sum_{i=1}^n x_i \leq k $
2. $ x_i \geq 0 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Maximize the reliability:
$$
\max_{x \in \mathbb{Z}_{\geq 0}^n,\, \sum x_i \leq k} \min_{1 \leq i \leq n} \sum_{j = \max(1, i - r)}^{\min(n, i + r)} (a_j + x_j)
$$
API Response (JSON)
{
"problem": {
"name": "G. Castle Defense",
"description": {
"content": "Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining s",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF954G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining s...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "今天你要带领一群精灵弓箭手保卫一座被愤怒的兽人军队攻击的城堡。城堡的三面被无法穿越的山脉保护，剩下的另一面是一堵长墙，被划分为 #cf_span[n] 个区段。目前，第 #cf_span[i] 个区段恰好有 #cf_span[ai] 名弓箭手。你知道，站在第 #cf_span[i] 区段的弓箭手可以射击攻击距离不超过 #cf_span[r] 的兽人，即所有满足 #cf_span[|i - j| ≤...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, r, k \\in \\mathbb{Z} $, with $ 1 \\leq n \\leq 500{,}000 $, $ 0 \\leq r \\leq n $, $ 0 \\leq k \\leq 10^{18} $. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}_{\\geq 0}^n $ be th...",
"is_translate": false,
"language": "Formal"
}
]
}