#P18341. Wavelike Finding

Wavelike Finding

Wavelike Finding

标准输入,标准输出。

本题给定两个固定参数 kk 和 WW。

对于一个长度恰好为 2k2k 的序列 a1,a2,…,a2ka_1,a_2,\ldots,a_{2k},如果

∑i=1k(k−i+1)(ai+a2k−i+1)≥W,\sum_{i=1}^{k}(k-i+1)(a_i+a_{2k-i+1})\ge W,

就称这个序列是 shaky 的。

对于一个序列 b1,b2,…,bmb_1,b_2,\ldots,b_m,如果它同时满足以下两条,就称它是 wavelike 的:

  • m≥2km\ge2k;
  • 它至少含有一个 shaky 子序列。这里的子序列不要求连续,但必须保持原来的相对顺序。

现在给定序列 s1,s2,…,sns_1,s_2,\ldots,s_n。请从中选择尽可能多段互不重叠的 wavelike 连续子序列。

被选的每一段必须是原序列中的一个连续区间;不同区间不能共用位置。这些区间不需要覆盖整个序列,可以在相邻两段之间留下未选的位置。

输入格式

第一行包含三个整数 n,k,Wn,k,W。

第二行包含 nn 个整数 s1,s2,…,sns_1,s_2,\ldots,s_n。

输出格式

输出一行一个整数,表示最多能够选出多少段互不重叠的 wavelike 连续子序列。

数据范围

  • 2≤n≤2⋅1052\le n\le2\cdot10^5;
  • 1≤k≤⌊n/2⌋1\le k\le\lfloor n/2\rfloor;
  • ∣W∣≤1017|W|\le10^{17};
  • ∣si∣≤106|s_i|\le10^6。

输入只有一组数据。

样例输入 1

9 2 25
6 4 3 5 7 1 2 5 8

样例输出 1

2

样例输入 2

9 2 30
6 4 3 5 7 1 2 5 8

样例输出 2

1

样例输入 3

2 1 1
0 0

样例输出 3

0

样例输入 4

2 1 -6
-1 -5

样例输出 4

1

样例说明

第三组样例中,唯一的两项子序列得分为0,小于1,因此答案为0。第四组样例中,两个数之和恰好为-6,满足大于等于门槛的要求,因此答案为1。