链接: https://cses.fi/problemset/task/3227

板块: Sliding Window Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一道栅栏由 $n$ 块竖直的木板组成。每块木板的宽度为 $1$，高度可以不同。

你想在栅栏上贴一个矩形广告。你的任务是，从左到右，在每 $k$ 块竖直木板组成的窗口中，计算这样一个广告能达到的最大面积。

输入

第一行包含两个整数 $n$ 和 $k$：栅栏的宽度和窗口大小。

在此之后，有 $n$ 个整数 $x_1, x_2, \dots, x_n$：每块木板的高度。

输出

输出 $n - k + 1$ 个整数：广告的最大面积。

数据范围

$1 \le k \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$

样例输入

8 3
4 1 5 3 3 2 4 1

样例输出

5 6 9 6 6 4