Мангасын Тоглоом I

2s

512MB

1750

0%

Advanced Techniques

$n$ шаттай тоглоом тоглож байна. Шат бүрт нэг мангас байна. $1,2,\dots,n-1$ -р шат дээр мангасыг алах эсвэл орхих боломжтой. Харин $n$ -р шатанд тоглоомдоо ялахын тулд сүүлчийн мангасыг заавал алах ёстой.

Мангас алахад $sf$ хугацаа шаардана; $s$ нь мангасын хүч, $f$ нь таны ур чадварын коэффициент (коэффициент бага байх тусам сайн). Мангас алсны дараа шинэ коэффициент авна. Тоглоомд ялахад шаардагдах хамгийн бага нийт хугацааг ол.

https://cses.fi/problemset/task/2084

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

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $x$ : шатуудын тоо ба ур чадварын анхны коэффициент.

Хоёр дахь мөрөнд $n$ бүхэл тоо $s_1,s_2,\dots,s_n$ : мангас бүрийн хүч.

Гурав дахь мөрөнд $n$ бүхэл тоо $f_1,f_2,\dots,f_n$ : мангас алсны дараах шинэ коэффициент.

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

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

Хязгаарлалт

$1 \le n \le 2 \cdot 10^5$
$1 \le x \le 10^6$
$1 \le s_1 \le s_2 \le \dots \le s_n \le 10^6$
$x \ge f_1 \ge f_2 \ge \dots \ge f_n \ge 1$

Жишээ

Оролт1

5 100
20 30 30 50 90
90 60 20 20 10

Гаралт1

0.1 / 64 KiB

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