CF954G Castle Defense

今天你将带领一队精灵弓箭手防守一座被愤怒兽人军队攻击的城堡。城堡的三面被无法逾越的高山保护，剩下的一面由一堵长墙守卫，这堵墙被分为 $n$ 个区段。此刻，第 $i$ 个区段上正好有 $a_i$ 名弓箭手。你知道，站在第 $i$ 个区段的弓箭手可以射击攻击距离不超过 $r$ 的区段的兽人，也就是说，所有满足 $|i-j|\leq r$ 的区段 $j$ 都能被第 $i$ 个区段的弓箭手射击。特别地，$r=0$ 表示弓箭手只能射击攻击自己所在区段的兽人。 定义第 $i$ 个区段的防御等级为能够射击攻击该区段兽人的弓箭手总数。防御方案的可靠性定义为所有区段防御等级的最小值。 现在距离兽人进攻还有一点时间，你无法重新分配已经在墙上的弓箭手，但你手中还有 $k$ 名预备弓箭手，可以任意分配到各个区段。你希望通过最优分配这 $k$ 名弓箭手，使得防御方案的可靠性最大。

输入的第一行包含三个整数 $n$、$r$ 和 $k$（$1\leq n\leq 500000$，$0\leq r\leq n$，$0\leq k\leq 10^{18}$），分别表示墙的区段数、弓箭手最大射击距离和可分配的预备弓箭手数量。第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\leq a_i\leq 10^9$），表示每个区段当前的弓箭手数量。

输出一个整数，表示通过最优分配 $k$ 名预备弓箭手后，防御方案可靠性的最大可能值，即所有区段防御等级的最大最小值。

由 ChatGPT 4.1 翻译