المپدیا

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

ابزار کاربر

ابزار سایت


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

Knight

شاید باورش برای ما سخت باشه ولی‌ متاسفانه همچنان کشورهایی هستند که در اعطای پست‌های مهم دولتی روابط را بر ضوابط ترجیح می‌دهند. نمونه بارز آن کشور دوست و همسایه ی قجبرستان است. در این کشور علیرغم این که رئیس جمهور به شدت با پارتی‌بازی مخالف است بعضی از‌ وزرای کابینه‌اش بسیار به پارتی‌بازی عشق می‌ورزند. ‎ سرآمد همه‌ی وزرا، وزیر شعر و طرب با نام کنستانتین اردشیری است که در وزارت‌خانه او بر حسب اتفاق نام‌خانوادگی همه اردشیری است. شاید باز هم برای ما عجیب باشد که تعداد زیادی از افراد ‎$2$‎ شغله در این وزارت‌خانه وجود دارد‎. ‎ رئیس جمهور که مورد هجوم انتقاد قرار گرفته بود کنستانتین را به دفتر خود فراخواند و او را مجبور کرد تا لااقل دو شغله‌گی را از بین ببرد. ‎ از این رو کنستانتین همه‌ی فامیل خود را جمع کرد و از آن‌ها خواست که هر کس کاری که مدنظرش است را اعلام کند. هر کس به ترتیب از دورترین فامیل تا نزدیک‌ترین آن‌ها که برادرش باشد شغلی‌ که می‌خواست را به وی گفت. او می‌داند که هر کس تنها در صورتی‌ کار می‌کند که به هیچ کسی‌ که در مقایسه باهاش از لحاظ نسبت به کنستانتین دورتر باشد کاری با ارزش‌تر داده نشود. دقت کنید هرکس یا کاری قبول نمی‌کند یا اگر قبول کند تنها شغل مدنظرش را قبول می‌کند. ‎$m$‎ کار وجود دارد که ارزش آن‌ها از ‎$1$‎ تا ‎$m$ (از کم به زیاد است).

همچنین وزیر می‌‌داند حداکثر ‎$w_i$‎ نفر می‌توانند در کار ‎$i$‎ام مشغول باشند. به او کمک کنید تا بیشترین افراد ممکن را استخدام کند. ‎

ورودی

  • در سطر اول ورودی به ترتیب ‎$(1 \leq n \leq 200000)$‎ که تعداد افراد فامیل و ‎$(1 \leq m \leq 200000)$‎ تعداد کار‌ها آمده است‎.‎
  • در سطر دوم ‎$n$‎ عدد بین ‎$1$‎ و ‎$m$‎ آمده که بیان گر شغل‌های مدنظر افراد فامیل از دورترینشان به نزدیک‌‌ترین است‎.‎
  • در سطر سوم ‎$m$‎ عدد بین ‎$1$‎ و ‎$n$‎ آمده که بیان‌گر ظرفیت هر کار از کم‌ارزش‌ترین به پرارزش‌ترین آن‌هاست.‎

خروجی

‎ یک عدد ‎$k$‎ که بیان‌گر تعداد افراد بیشینه‌ایست که به آن‌ها کار داده شده است را در خروجی چاپ کنید.‎

محدودیت‌ها

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

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

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

ابزار صفحه