← 返回题目列表

AtCoder · tkppc4_2_f

F. Segtree☆魔法

中文机器翻译题面 查看原题

配点 700 点

問題文

魔法少女塔普莉斯女士Segtree 获得了一根魔法棒。塔普莉斯女士对自己低质量的扮演者们感到生气,决定使用这根魔杖击败这些扮演者。
N 扮演者的身体排成一条直线,从左至右顺序排列 1 减去 N 。i 第几位扮演者的体力为 A_i 。塔普莉斯女士接下来可以按照自己喜欢的顺序,进行任意次数的攻击,K 以上 N-K+1 攻击以下编号的对手。
Segtree 是范围攻击型武器,当塔普莉斯女士 x 第几位对手以 Segtree 攻击时, y 第几位对手将受到 max(0, K-|x-y|)^2 的伤害。
由于塔普莉斯女士是善良的天使,她不会将对手的体力攻击到低于零。在遵守此条件的前提下,请判断是否有可能把所有对手全部击倒,即将所有对手的体力恰好降为零。


入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 ... A_{N-1} A_N

出力

如果有可能将所有对手的体力恰好降为零 Yes,否则 输出 No 。

制約

  • 所有输入均为整数。
  • 3 \leq N, K \leq 133 \ 333
  • 2K-1 \leq N
  • 0 \leq A_i \leq 10^{13}

小課題

这项作业需要 2 有两个子作业。
  1. (200 点) N, K \leq 1 \ 333
  2. (500分)没有额外限制。

入力例1

8 3
1 4 10 9 14 13 5 1

出力例1

Yes

例如,3番目、5番目、6按此顺序攻击第几位对手 Segtree 命中时,体力的数值会如以下方式变化。

  • 首先, 交换第3 击中第几号对手。对手的体力从左到右依次是 {0, 0, 1, 5, 13, 13, 5, 1} 。
  • 接下来,5 击中第几号对手。对手的体力从左到右依次是 {0, 0, 0, 1, 4, 9, 4, 1} 。
  • 接下来,6 击中第几号对手。对手的体力从左到右依次是 {0, 0, 0, 0, 0, 0, 0, 0} 。
如果按照那样进行命中,Segtree 可以将所有对手的体力恰好降为零。

入力例2

6 3
8 6 9 1 2 1

出力例2

No

无论以何种方式攻击,都无法将所有对手的体力恰好降为零。

入力例3

16 4
2 9 22 41 34 20 20 37 71 72 55 36 15 5 1 0

出力例3

Yes

作者: ynym小笼包