#P2800. [Poi2012]Leveling Ground

    ID: 1908 传统题 1000ms 512MiB 尝试: 139 已通过: 58 难度: 9 上传者: 标签>CF2700省选/NOI-差分转化线性不定方程扩展欧几里得算法模逆元有限候选集缩减凸性/单峰性判定堆贪心交换论证鸣谢oimaster

[Poi2012]Leveling Ground

题目描述

给出n个整数 X1,X2,...XnX_1,X_2,...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},...,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},...,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},...,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},...,X_r都减去bb。 求最少的操作次数将Xi{X_i}全部变成00。

输入格式

第一行三个正整数nn,aa,bb。 第二行nn个整数,依次表示X1,X2,...XnX_1,X_2,...X_n 。

输出格式

一个非负整数,表示最少的操作次数。如果不存在方案,输出−1-1。

输入样例

5 2 3
1 2 1 1 -1

输出样例

5

数据规模与约定

1≤n≤1051\le n\le10^5,1≤a,b≤1091\le a,b\le10^9,∣Xi∣≤109|X_i|\le10^9。操作过程中允许地面高度为负数。

题目来源