P0695

[Poi2012]Leveling Ground

[Poi2012]Leveling Ground

给出 nn 个整数 X1,X2,…,XnX_1,X_2,\ldots,X_n，以及两个正整数 aa、bb。可以进行以下四种操作：

  1. 选择正整数 l,rl,r，满足 1≤l≤r≤n1\le l\le r\le n，将 Xl,Xl+1,…,XrX_l,X_{l+1},\ldots,X_r 都加上 aa。
  2. 选择正整数 l,rl,r，满足 1≤l≤r≤n1\le l\le r\le n，将 Xl,Xl+1,…,XrX_l,X_{l+1},\ldots,X_r 都减去 aa。
  3. 选择正整数 l,rl,r，满足 1≤l≤r≤n1\le l\le r\le n，将 Xl,Xl+1,…,XrX_l,X_{l+1},\ldots,X_r 都加上 bb。
  4. 选择正整数 l,rl,r，满足 1≤l≤r≤n1\le l\le r\le n，将 Xl,Xl+1,…,XrX_l,X_{l+1},\ldots,X_r 都减去 bb。

求将所有 XiX_i 都变为 00 所需的最少操作次数。如果不存在可行方案，输出 −1-1。

时间限制：10000 ms10000\ \mathrm{ms}。
内存限制：65536 KB65536\ \mathrm{KB}。

输入格式

第一行包含三个正整数 n,a,bn,a,b，满足 n≤105n\le 10^5 且 a,b≤109a,b\le 10^9。

第二行包含 nn 个整数，依次表示 X1,X2,…,XnX_1,X_2,\ldots,X_n，满足 ∣Xi∣≤109|X_i|\le 10^9。

输出格式

输出一个整数，表示将所有 XiX_i 都变为 00 所需的最少操作次数。如果不存在可行方案，输出 −1-1。

样例输入

5 2 3
1 2 1 1 -1

样例输出

5

样例解释

可以进行以下 55 次操作将所有 XiX_i 都变为 00：

  1. 将 X1,X2X_1,X_2 都加上 22，数组变为 3,4,1,1,−13,4,1,1,-1。
  2. 将 X1,X2X_1,X_2 都减去 33，数组变为 0,1,1,1,−10,1,1,1,-1。
  3. 将 X2,X3,X4,X5X_2,X_3,X_4,X_5 都加上 22，数组变为 0,3,3,3,10,3,3,3,1。
  4. 将 X5X_5 加上 22，数组变为 0,3,3,3,30,3,3,3,3。
  5. 将 X2,X3,X4,X5X_2,X_3,X_4,X_5 都减去 33，数组变为 0,0,0,0,00,0,0,0,0。

数据范围

  • nn、aa、bb 为正整数，且 n≤105n\le 10^5、a,b≤109a,b\le 10^9。
  • 对于所有 ii，均有 ∣Xi∣≤109|X_i|\le 10^9。

来源与许可

本题为 POI 2012 试题「Leveling Ground」，题面与测试数据整理自 BZOJ 2800。

样例 1

输入

5 2 3
1 2 1 1 -1

输出

5