المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۶:سوال ۱۸

Tele

ﺩﺭ ﮐﻮﻫﺴﺘﺎﻥﻫﺎﯼ ﯾﻮﺗﻮﭘﯿﺎ ﺩﺭ ﮐﺸﻮﺭ ﺍﻟﻤﭙﯿﺎﺩﯼﻫﺎ $n$ ﮐﻮﻩ ﺑﻪ ﺗﺮﺗﯿﺐ ﺩﺭ ﯾﮏ ﺭﺩﯾﻒ ﻗﺮﺍﺭ ﺩﺍﺭﻧﺪ. ﺍﺭﺗﻔﺎﻉ کوه $i$ام $h_i$ می‌باشد. باشگاه دانش‌پژوهان جوان در صدد ساخت یک ﺗﻠﻪﮐﺎﺑﯿﻦ ﺩﺭ ﺍﯾﻦ ﮐﻮﻫﺴﺘﺎﻥ ﻣﯽﺑﺎﺷﺪ. ﺍﯾﻦ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺩﻭ ﺳﺮ ﺩﺍﺭﺩ ﮐﻪ ﺗﻮﺳﻂ ﯾﮏ ﺳﯿﻢ ﺭﺍﺳﺖ ﺑﻪ ﻫﻢ ﻣﺘﺼﻞ ﻣﯽﺑﺎﺷﻨﺪ. ﺍﯾﻦ ﺩﻭ ﺳﺮ ﺑﺎﯾﺪ ﺭﻭﯼ ﺩﻭ ﮐﻮﻩ ﻣﺘﻔﺎﻭﺕ ﺳﺎﺧﺘﻪ ﺷﻮﻧﺪ. ﻫﻤﭽﻨﯿﻦ ﺩﻭ ﺳﺮ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺑﺎﯾﺪ ﻫﻢﺍﺭﺗﻔﺎﻉ ﺑﺎﺷﻨﺪ. ﺩﺭ ﻧﺘﯿﺠﻪﯼ ﺳﺎﺧﺖ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺭﻭﯼ ﮐﻮﻩﻫﺎﯼ $i$ام و $j$ام تنها در صورتی ممکن است که تمامی کوه‌های $i$ام تا $j$ام (شامل خود کوه $i$ و $j$) ارتفاعشان به $min(h_i,h_j)$ کاهش یابد. بدیهی است کوهی که ارتفاعش ﺍﺯ ﺍﯾﻦ ﻣﻘﺪﺍﺭ کم‌تر ﺍﺳﺖ ﻣﺸﮑﻠﯽ ﺍﯾﺠﺎﺩ ﻧﻤﯽﮐﻨﺪ.

ﺍﺩﺍﺭﻩ ﺭﺍﻩﺳﺎﺯﯼ ﺍﻟﻤﭙﯿﺎﺩﯼﻫﺎ ﺑﻪ ﺑﺎﺷﮕﺎﻩ ﻗﻮﻝ ﺩﺍﺩﻩ ﺑﻪ ﺍﺯﺍﯼ ﻫﺰﯾﻨﻪ $p$ تومان می‌تواند $p$ متر از ارتفاع یک کوه را کم کند.

ﺑ‰ﺮﺍﯼ این‌که ﺍﯾ‰ﻦ ﺗ‰ﻠ‰ﻪﮐ‰ﺎﺑ‰ﯿ‰ﻦ ﺑ‰ﺮﺍﯼ ﺑ‰ﭽ‰ﻪﻫ‰ﺎ ﺟ‰ﺬﺍﺏ ﺑ‰ﺎﺷ‰ﺪ، ﺑ‰ﺎﺷ‰ﮕ‰ﺎﻩ ﻗ‰ﺼ‰ﺪ ﺩﺍﺭﺩ ﺍﯾ‰ﻦ ﺗ‰ﻠ‰ﻪﮐ‰ﺎﺑ‰ﯿ‰ﻦ ﺭﺍ ﻃ‰ﻮﺭﯼ ﺑ‰ﺴ‰ﺎﺯﺩ ﮐ‰ﻪ ﺍﺯ ﺭﻭﯼ ﺣ‰ﺪﺍﻗ‰ﻞ $k$ کوه (با احتساب ﺩﻭ ﮐ‰ﻮﻫ‰ﯽ ﮐ‰ﻪ ﺗ‰ﻠ‰ﻪ ﮐ‰ﺎﺑ‰ﯿ‰ﻦ ﺑ‰ﺮ ﺭﻭﯼ ﺁﻥﻫ‰ﺎ ﺳ‰ﺎﺧ‰ﺘ‰ﻪﺷ‰ﺪﻩ ﺍﺳﺖ) ﻋﺒﻮﺭ ﮐﻨﺪ.

ﺑ‰ﻪ ﺑ‰ﺎﺷ‰ﮕ‰ﺎﻩ ﮐ‰ﻤ‰ﮏ ﮐ‰ﻨ‰ﯿ‰ﺪ ﺑ‰ﺎ کم‌ترین ﻫ‰ﺰﯾ‰ﻨ‰ﻪ ﻣ‰ﻤ‰ﮑ‰ﻦ ﻃ‰ﻮﺭﯼ ﺍﯾ‰ﻦ ﮐ‰ﻮﻩﻫ‰ﺎ ﺭﺍ ﮐ‰ﻮﺗ‰ﺎﻩ ﮐ‰ﻨ‰ﺪ، ﮐ‰ﻪ ﺑ‰ﺘ‰ﻮﺍﻧ‰ﺪ ﯾ‰ﮏ ﺗﻠﻪﮐﺎﺑﯿﻦ ﮐﻪ ﺍﺯ ﺭﻭﯼ ﺣﺪﺍﻗﻞ $k$ کوه ﻋﺒﻮﺭ ﻣﯽﮐﻨﺪ، ﺑﺴﺎﺯﺩ.

ورودی

ﺩﺭ ﺳﻄﺮ ﺍﻭﻝ ﻭﺭﻭﺩﯼ $n$ و $k$ آمده است.($1\leq n \leq 3\times 10^5$ و $1\leq k \leq n$)

در سطر بعدی، $n$ عدد آمده که عدد $i$ام ارتفاع کوه $i$ام را مشخص می‌کند.

خروجی

ﺩﺭ ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮﻭﺟﯽ کم‌ترین ﻫﺰﯾﻨﻪ ﻻﺯﻡ ﺑﺮﺍﯼ ﺳﺎﺧﺖ ﺍﯾﻦ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺭﺍ ﺑﻨﻮﯾﺴﯿﺪ.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۶۴ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 4
1 3 2 4 1
6

ابزار صفحه