Лифтийн Явуулалтууд

2s

512MB

1359

0%

Dynamic Programming

Зөвхөн нэг лифтэй барилгын орой дээр гарахыг хүссэн $n$ хүн байна. Хүн бүрийн жин болон лифтэд зөвшөөрөгдөх дээд жин мэдэгдэнэ. Хамгийн бага хэдэн лифтийн явуулалт хэрэгтэй вэ?

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

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

Эхний мөрөнд хоёр бүхэл тоо $n$ , $x$ байна: хүмүүсийн тоо, лифтэд зөвшөөрөгдөх дээд жин.

Хоёр дахь мөрөнд хүн бүрийн жин $w_1,w_2,\dots,w_n$ $n$ бүхэл тоо байна.

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

Нэг бүхэл тоо хэвлэ: явуулалтын хамгийн бага тоо.

Хязгаарлалт

$1 \le n \le 20$
$1 \le x \le 10^9$
$1 \le w_i \le x$

Жишээ

Оролт1

4 10
4 8 6 1

Гаралт1

0.1 / 64 KiB

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