#P18942. [Mladen Manev 2020 A3] pebbles / 石子游戏

[Mladen Manev 2020 A3] pebbles / 石子游戏

石子游戏(Pebbles)

题目描述

有 NN 堆石子,从左到右编号为 1…N1\ldots N,第 ii 堆初始有 aia_i 颗石子。

一次操作选择一个连续区间,要求区间中的每堆当前至少有一颗石子,然后从其中的每堆各取走一颗。已经变空的石堆仍占据原来的位置,后续操作不能选择包含它的区间。

你可以进行至多 KK 次操作。求最多可以使多少堆石子变空。

输入格式

第一行两个整数 N,KN,K。第二行 NN 个正整数 a1,…,aNa_1,\ldots,a_N。

输出格式

输出能够清空的最多石堆数。

数据范围

1≤N≤20001\le N\le2000,1≤K≤1091\le K\le10^9,1≤ai≤1091\le a_i\le10^9。

样例

6 5
1 5 3 2 1 4
5

来源与数据说明

2020 年 Dr. Mladen Manev,A3,原题名 pebbles。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。