#P5625. 「一本通 5.5 练习 1」烽火传递

    ID: 4626 传统题 1000ms 256MiB 尝试: 130 已通过: 26 难度: 4 上传者: 标签>难度分类普及+/提高-动态规划线性 DP单调队列优化 DP排序与序列处理单调队列CF1600单调队列/单调栈优化

「一本通 5.5 练习 1」烽火传递

「一本通 5.5 练习 1」烽火传递

题目描述

两个城市之间依次建有 nn 座烽火台,第 ii 座烽火台发出信号的代价是 aia_i。要求任意连续的 mm 座烽火台中至少有一座发出信号。求满足条件的最小总代价。如果 m>nm>n,不存在长度为 mm 的连续区间,最小总代价为 00。

输入格式

第一行两个整数 n,mn,m。第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一行一个整数,表示最小总代价。

样例 1

5 3
1 2 5 6 2
4

样例中选择第 22 座和第 55 座烽火台,总代价为 44。

数据范围

1≤n,m≤2×1051\le n,m\le2\times10^5,1≤ai≤10001\le a_i\le1000。