Гулгуур цонхны өртөг

2s

512MB

1940

0%

Sliding Window Problems

$n$ бүхэл тоо бүхий массив өгөгдсөн. Зүүнээс баруун тийш $k$ элемент бүхий цонх бүрийн хувьд бүх элементийг тэнцүү болгох хамгийн бага нийт өртгийг ол.

Элемент бүрийг өртөг $x$ -тэйгээр нэмэгдүүлэх эсвэл бууруулж болно; $x$ нь шинэ ба анхны утгын зөрүү. Нийт өртөг нь эдгээр өртгүүдийн нийлбэр.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $k$ байна: элементийн тоо ба цонхны хэмжээ.

Дараа нь $n$ бүхэл тоо $x_1,x_2,\ldots,x_n$ байна: массивын утгууд.

Гаралтын формат

$n-k+1$ утга хэвлэ: өртгүүд.

Хязгаарлалт

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

Жишээ

Оролт1

8 3
2 4 3 5 8 1 2 1

Гаралт1

2 2 5 7 7 1

0.1 / 64 KiB

Редактор уншиж байна...