سلام دوست عزیز😃👋

به مسابقه «کدکاپ ۸ - دست‌گرمی» خوش آمدی!

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

این مسابقه هیچ تاثیری در رقابت‌های کدکاپ ندارد و صرفاً برای دست‌گرمی شما است.

موفق باشید و بهتون خوش بگذره 😉✌

آبمیوه


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

امین وارد یک آب‌میوه فروشی می‌شود. معده امین VV لیتر ظرفیت آب‌میوه دارد!

در این آب‌میوه فروشی nn نوع آب‌میوه وجود دارد. انواع آب‌میوه را با اعداد 11 تا nn شماره‌گذاری می‌کنیم. از آب‌میوه‌ی نوع iiام (1in1 \leq i \leq n) به اندازه‌ی viv_i لیتر در مخزن آن وجود دارد.

امین می‌داند که اگر همه‌ی ظرف آب‌میوه‌ی موجود در مخزن iiام را بنوشد، به اندازه‌ی hih_i خوشحال می‌شود. همچنین اگر هر کسری از این ظرف را بخورد به همان نسبت خوشحالی بدست می‌آورد. (برای مثال اگر 13vi\frac{1}{3} v_i لیتر بنوشد به‌اندازه‌ی 13hi\frac{1}{3} h_i خوشحالی بدست می‌آورد.)

حال امین می‌خواهد از هر نوع آب‌میوه مقداری بنوشد. (این مقدار می‌تواند هر عدد حقیقی نامنفی باشد!) به طوری که مجموع خوشحالی او بیشینه باشد.

از شما می‌خواهیم برنامه‌ای بنویسید که این مقدار بیشینه را محاسبه و چاپ کند.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت nn و VV داده می‌شود. 1n1000001 \leq n \leq 100 \, 000 1V1091 \leq V \leq 10^9

در nn سطر بعدی، در هر سطر، دو عدد hih_i و viv_i که با یک فاصله از هم جدا شده‌اند. 1hi,vi1091 \leq h_i, v_i \leq 10^9

خروجی🔗

در تنها سطر خروجی، حداکثر مجموع خوشحالی که امین می‌تواند بدست بیاورد را چاپ کنید.

خروجی برنامه را با دقت دقیقاً یک رقم بعد از اعشار چاپ کنید.

مثال‌ها🔗

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

3 400
100 200
150 140
100 300
Plain text

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

270.0
Plain text

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

1 10
500 30
Plain text

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

166.7
Plain text
راهنمایی اول

ابتدا مسئله را برای حالت n=2n = 2 حل کنید.

راهنمایی دوم

اکنون که می‌توانید تصمیم بگیرد بین دو آبمیوه کدامیک الویت دارد. سعی کنید با همین روش همه‌ی آبمیوه‌ها را مرتب کنید.

راهنمایی سوم

برای اینکه این مرتب‌سازی سریع باشد، سعی کنید از روش‌های مرتب‌سازی مقایسه‌ای مثل merge sort یا quick sort استفاده کنید تا به‌اندازه‌ی کافی راه‌حل شما سریع باشد.

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