QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+1]
Statistics

时间限制:2 秒,空间限制:512 MB。

题目描述

长度为 n 的街道被积雪覆盖,将街道划分为 n 段,第 i 段的积雪量为 ai,保证 0aimai 为整数。

天依与言和要来清理积雪,每次清理有 2 种选择:

  • 天依从位置 1 走到位置 x,将积雪清理掉 c,再走回位置 1。同时,因为在雪地上移动,位置 1x 的积雪量减少 1,即 i[1,x1],ai:=ai1,ax:=axc1
  • 言和从位置 n 走到位置 x,将积雪清理掉 c,再走回位置 n。同时,因为在雪地上移动,位置 xn 的积雪量减少 1,即 i[x+1,n],ai:=ai1,ax:=axc1

任意时刻,积雪量对 0max

天依与言和想知道,最少进行多少次清理后(即最小化两人清理次数总和),能将所有积雪清除,即 \forall i \in [1, n], a_i = 0

输入格式

本题有多组测试数据。

首先输入一行两个数 T, tidT 表示数据组数,tid 表示子任务编号(样例的子任务编号为 0)。

对于每组数据:

第一行三个整数 n, m, c

第二行 n 个整数 a_1 \sim a_n

输出格式

对于每组数据,输出一行一个整数表示答案。

测试样例

样例输入 1

1 0
5 5 1
1 3 2 3 1

样例输出 1

2

样例解释 1

天依走到位置 4 清理,积雪量变为 [0, 2, 1, 1, 1]

言和走到位置 2 清理,积雪量变为 [0, 0, 0, 0, 0]

共 2 次清理。

样例 2

见附加文件中的 snow.insnow.ans。这个样例中有 100 组 n = 10, m = 10 的数据。

数据范围

对于 100\% 的数据,1 \le T \le 10^51 \le n, m \le 5 \times 10^5\sum n, \sum m \le 10^60 \le a_i \le m0 \le c \le 5 \times 10^5

子任务编号 n m 特殊限制 分值 子任务依赖
1 \le 5 \times 10^5 \leq 5 \times 10^5 c = 0 2
2 \leq 2 3
3 \leq 5 \leq 5 T \le 10^5 4
4 \leq 50 \leq 50 \sum n, \sum m \le 200 10 3
5 \leq 300 \leq 300 \sum n, \sum m \le 600 10 4
6 \leq 2\,000 \leq 2\,000 \sum n, \sum m \le 4000 10 5
7 \leq 5 \times 10^4 \leq 5 \times 10^4 c \le 20, \sum n, \sum m \le 10^5 20
8 \sum n, \sum m \le 10^5 15 6, 7
9 \leq 5 \times 10^5 \leq 5 \times 10^5 c \le 20 10 1, 7
10 15 2, 8, 9