#3243. 「COCI 2020.1」Holding

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 COCI 2019/2020 Contest #4 T3「Holding」

Ivica 和他的资产——一个他拥有的,由 N 个克罗地亚企业组成的财团,正在经历一段困难的时间。每家企业都有负债,所以政府派公职律师拿走他的一切财产。只有我们发现了尽管他有着巨额的欠债,Ivica 还是成功地让政府留给他了某些企业。是哪些呢?我们也知道了。

公职律师在桌子上摆出了 N 份 Ivica 的公司的专有文件。第一个公司的债务数额写在第一份文件上,数额是 A_1 ,第二个公司的债务数额写在第二份文件上,数额是 A_2 ,……,最后一家公司的债务数额写在最后一份文件上,数额是 A_N 。Ivica 成功留下了公司 A_L,A_{L+1},\ldots ,A_R ,这里 L,R 表示桌子上文件的位置。Ivica 很幸运,因为公职律师(也)是腐败的。他们会让他拿走编号从 L R 的文件,但是他们会让他以特定的代价交换任意两份文件。更确切地说,交换位置 i j 的文件会花费 |i-j| 库纳(克罗地亚货币)。Ivica 目前很绝望,他口袋里只有 K 库纳,他想要使得留下的公司负债越少越好。

请帮他达成目标。


一句话题意

给定一个长为 N 的数组 A ,可以多次交换两个数的位置,代价为两个位置下标差的绝对值。现在给定 L,R ,求在代价和不超过 K 的情况下, A 数组中 [L,R] 的区间和的最小值。

输入格式

第一行四个整数 N,L,R,K ,意义同题目描述;

第二行 N 个整数 A_i ,意义同题目描述。

输出格式

输出一行一个整数,表示最优情况下花 K 库纳能够留下公司的最小负债钱数。

样例

样例输入 1

3 2 2 1
1 2 3

样例输出 1

1

样例输入 2

5 2 3 3
21 54 12 2 0

样例输出 2

12

样例输入 3

6 4 6 100
1 2 3 4 5 6

样例输出 3

6

数据范围与提示

对于全部数据, 1\le L\le R\le N\le 100,0\le K\le 10^4,0\le A_i\le 10^6

详细子任务附加限制及分值如下表:

子任务编号 附加限制 分值
1 N\le 13,R=N 20
2 N\le 50,R=N 30
3 N\le 50
4 无附加限制 20