Problem 7C. 分发物资

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 7C. 分发物资

题目描述

现在数轴的 \(1,2\cdots ,n\) 处各有一个人,他们各需要 \(a_1,a_2,\cdots ,a_n\) 的物资。

因此,你准备了 \(m=\sum_{i=1}^n a_i\) 份物资准备分发。

给定参数 \(k\),你可以进行以下操作:

  • 花费 \(1\) 的时间,选择一段区间 \([l, r]\),且满足\(1\le l\le r\le n\) 和 \(r-l+1\le k\), 并且你的剩余物资数至少要有 \(r-l+1\) 份 。接下来,向数轴上位置为 \(l,l+1,\cdots ,r\) 的人各分发一份物资。

求至少需要多少时间,才能满足所有人的需求。

输入格式

第一行两个整数 \(n,k\),表示需要分发的人数和每次最多分发的人数。

第二行 \(n\) 个整数 \(a_i\),表示每个人需要物资的份数。

输出格式

仅一个整数,表示至少需要的时间。

样例输入1

4 2
1 4 2 1

样例输出1

5

样例1解释

每次至多分发给连续的两个人。

操作如下:

1 1 0 0

1 2 2 0

1 3 2 0

1 4 2 0

1 4 2 1

样例输入2

7 4
1 5 2 4 2 4 2

样例输出2

9

数据范围与约定

对于 \(40\%\) 的数据,\(n=k=2\)。

对于另外 \(20 \%\) 的数据,\(k=n\)。

对于另外 \(20\%\) 的数据,\(1\le n,a_i\le 100\)。

以上三部分数据不重合,占本题 \(80\%\) 的分数。

对于 \(100\%\) 的数据,\(1\le k\le n\le 5\times 10^5\),\(1\le a_i\le 10^9\)

注意,答案可能超过 \(32\) 位整数可以表示的范围。

2023秋 悬赏令第七周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-11-19 18:30
结束于
2023-11-26 00:00
持续时间
149.5 小时
主持人
参赛人数
48