مین‌ها


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

بهراد nn مین در یک ردیف پیدا کرده است که مین iiام در مختصات xix_i محور اعداد قرار دارد. او که می‌خواهد محیط را مین‌زدایی کند، تصمیم گرفته همه مین‌ها را منفجر کند.

برای انفجار هر مین باید نیرویی به آن وارد شود. اگر به یک مین به اندازه kk (k1)(k \ge 1) نیرو وارد شود،‌ مین منفجر شده و به تمام مین‌هایی که در فاصله کمتر مساوی kk از آن مین قرار دارند نیز به اندازه kk نیرو وارد می‌کند (که باعث انفجار آن‌ها نیز می‌شود).

هر بار بهراد می‌تواند نیرویی به یک مین وارد کند و کل نیرویی که مصرف می‌کند برابر است با جمع همه نیرو‌هایی که مستقیما به مین‌ها وارد کرده است.

بهراد می‌خواهد بداند که حداقل چقدر نیرو لازم دارد تا همه مین‌ها را منفجر کند.

ورودی🔗

در خط اول ورودی عدد nn، تعداد مین‌ها، آمده‌است.

در خط دوم nn عدد آمده است که عدد iiام، xix_i، مکان مین iiام را که عددی صحیح است نشان می‌دهد.

1n3×1051 \le n \le 3\times10^5 0xi10180 \le x_i \le 10^{18}

دنباله xx اکیدا صعودی است.

خروجی🔗

در تنها خط خروجی حداقل نیروی لازم برای منفجر کردن همه مین‌ها را چاپ کنید.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۲۵ 1n20001 \le n \le 2000
۲ ۳۵ 1n105,0xi2×1051 \le n \le 10^5, 0 \le x_i \le 2\times10^5
۳ ۴۰ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

4
1 3 10 12
Plain text

خروجی نمونه ۱🔗

4
Plain text

ورودی نمونه ۲🔗

8
0 1 4 5 8 9 12 13
Plain text

خروجی نمونه ۲🔗

3
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.