• هجدهمین مسابقه‌ی برنامه نویسی اینترنتی ایران
  • مقدماتی منطقه‌ی غرب آسیا، سایت تهران
  • دانشگاه صنعتی شریف، ۲۵ اسفند ۱۴۰۱

لینک‌های مفید برای شرکت در مسابقه:

کلاس طراحی الگوریتم


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

بهرام و محسن که تصمیم گرفته بودند با کمک یکدیگر تدریس کلاس طراحی الگوریتم ها را بر عهده بگیرند به تازگی با یک مشکل اساسی مواجه شده‌اند و قرار است راهشان را از هم جدا کنند. ریشه‌ی مشکل نگرش نابخردانه‌ی محسن در تشخیص استعداد یک دانشجو در طراحی الگوریتم است. بهرام بدرستی معتقد است که استعداد طراحی الگوریتم دانشجویان با میزان استعداد آن‌ها در ریاضیات گسسته رابطه‌ی مستقیم دارد. اما محسن می‌گوید دانشجویی که ریاضیات پیوسته را بهتر بفهمد طراح الگوریتم بهتری خواهد شد. بدین ترتیب قرار بر آن شد که دانشجویان کلاس را به دو گروه تقسیم کرده و هر کدام تدریس گروهی را به عهده بگیرند. تقسیم اعضای کلاس بدین صورت است که هر کس در نوبت خود یک دانشجو را انتخاب می‌کند سپس نوبت انتخاب را به دیگری واگذار می‌کند. این رویه تا انتخاب شدن تمام دانشجویان ادامه دارد. از آنجایی که بهرام اخلاقی پهلوانی دارد و روی خامی محسن حساب ویژه‌ای باز کرده است اجازه می‌دهد اولین انتخاب بر عهده‌ی محسن باشد. محسن نابخرد از استراتژی خبیصانه استفاده می‌کند. به این صورت که هر بار از بین دانشجویان باقیمانده فردی که بیشترین استعداد ریاضیات پیوسته را دارد انتخاب می‌کند. اگر چندین دانشجو با این شرایط وجود داشته باشد، محسن یکی از آن‌ها را به دلخواه خودش انتخاب می‌کند. بهرام به دلیل شناخت عمیقی که از محسن دارد خبیصانه بودن او را حدس زده و می‌خواهد بداند بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی خودش، مستقل از حرکات محسن، چند است. با محاسبه‌ی این مقدار به کمک بهرام بشتابید.

ورودی🔗

در خط اول ورودی عدد nn که بیانگر تعداد دانشجویان است به شما داده می‌شود. 1n1000001 \leq n \leq 100 \, 000

در هر یک از خطوط دوم و سوم به ترتیب nn عدد صحیح a1,a2,,ana_1, a_2, \dots, a_n\, و b1,b2,,bnb_1, b_2, \dots, b_n\, داده می‌شود که aia_i بیانگر استعداد دانشجوی ii در ریاضیات پیوسته و bib_i بیانگر میزان استعداد دانشجوی ii در ریاضیات گسسته است.

1ai,bi1091 \leq a_i, b_i \leq 10^9

خروجی🔗

در خروجی بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی توسط بهرام را با فرض خبیصانه بودن استراتژی محسن چاپ کنید.

مثال‌ها🔗

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

3
1 8 4
12 11 1
Plain text

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

12
Plain text

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

5
1 2 3 4 5
2 3 4 5 6
Plain text

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

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