Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۳۱:عملی نهایی اول:سوال ۲

گل (Flower)

مالک بعد از تصاحب ثروت ریزآبادی‌ها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و در آن n گل در یک ردیف کاشت. هر گل بویی دارد و iامین بو از سمت چپ ai واحد بو دارد. میثم هر روز هنگام غروب خورشید، به باغش می‌رود و از سمت چپ به سمت راست باغ حرکت می‌کند. اگر به گلی برسد که بوی آن را حس نکند بسیار خشمگین می‌شود و تمام باغ را آتش می‌زند. او بوی گل i>1 را حس نمی‌کند اگر ai<ai1 باشد.

مالک که از این موضوع آگاه است n تا اسپری خریده است تا هر روز صبح به گل‌ها بزند و بوی آن‌ها را فقط در آن روز مقداری بیشتر کند. برای اینکه بوی گل iام را یک واحد افزایش دهد، باید یک پیس از اسپری iام به آن بزند. قیمت هر پیس از اسپری iام bi تومان می‌باشد. گاهی اسپری‌ها کیفیت لازم را ندارند و قیمت آن‌ها منفی می‌شود! قابل ذکر است که بوی گل‌ها نمی‌تواند از 106 بیشتر شود.

مالک در q روز بعدی، وقتی به باغ برود بوی یکی از گل‌ها افزایش می‌یابد. در روز iام مقدار axi به اندازه yi>0 بیشتر می‌شود. او که بسیار پول‌پرست است، می‌خواهد با کمترین هزینه ممکن، هر روز باغ را باب میل پسرش کند. به او کمک کنید تا این هزینه را در هر روز پیدا کند.

ورودی

در خط اول n و q، تعداد گل‌ها و تعداد روزها به‌ترتیب می‌آیند.

در خط دوم n عدد a1,a2,...,an به‌ترتیب می‌آیند.

در خط سوم n عدد b1,b2,...,bn به‌ترتیب می‌آیند.

در iامین خط از q خط بعدی، دو عدد yi و xi به‌ترتیب می‌آیند.

خروجی

در q خط، به ازای هر روز که مالک وارد باغ می‌شود، کمترین هزینه برای اینکه باغ را باب میل میثم کند را چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۷ نمره): n,q300
  • زیرمسئله دوم (۶ نمره): n,q5000 و 0bi
  • زیرمسئله سوم (۱۹ نمره): n,q5000
  • زیرمسئله چهارم (۲۲ نمره): 0bi
  • زیرمسئله پنجم (۴۶ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • 2n,q200000
  • 106ai,bi106
  • 1xn
  • تضمین می‌شود بوی تمامی گل‌ها هیچوقت از 106 بیشتر نمی‌شود.

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

ورودی نمونه خروجی نمونه
3 3
4 9 6
-1 3 0
3 4
1 6
3 5
-5
3
3
6 3
3 1 3 2 4 4
1 -5 1 1 1 1
1 3
5 6
2 999999
-1000008
-1000014
3999981

در نمونه اول، روز اول دنباله گل‌ها 4,9,10 می‌باشد. مالک می‌تواند ۵ بار به اولین گل اسپری بزند و دنباله گل‌ها 9,9,10 می‌شود و ۵- تومان خرج کند.

در روز دوم دنبال بوی گل‌ها 10,9,10 می‌باشد. مالک می‌تواند یک بار به دومین گل اسپری بزند و دنباله گل‌ها 10,10,10 می‌شود و ۳ تومان خرج کند.

در روز سوم دنباله گل‌ها 10,9,15 می‌شود و مشابه روز دوم کافی است مالک یک بار به دومین گل اسپری بزند.


ابزار صفحه