- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
کارل مارکس، بنیانگذار فقید کمونیسم، به دنبال بیشترین بهره‌وری از افراد با بهره‌مند کردن آن‌ها از حداقل حقوق است. او می‌داند که یکسری کار در جامعه با سختی بخصوص وجود دارد. از طرفی جامعه تعدادی نیروی کار دارد که در ماه اگر بیش از حد مشخص سختی بکشند، تلف می‌شوند. او همچنین توانایی هر کس در هر کار را نیز شناسایی کرده‌است و به عبارت دیگر اگر سختی یک کار $h$ و توانایی یک فرد در آن $s$ باشد، $\frac{h}{s}$ ساعت طول می‌کشد تا آن شخص به تنهایی آن کار را تمام کند و متحمل $h$ واحد سختی شود. توجه کنید که هر فرد می‌تواند کل یک کار و یا تنها بخشی از آن را انجام دهد و به میزان آن بخش سختی و طول کشیدنش خواهد بود.
کارل مارکس به هر کس به میزان ساعت کاری وی در ماه حقوق می‌دهد و از شما کمک می‌خواهد تا کمینه مجموع حقوق افراد را برای انجام تمام کارها بیابید. متأسفانه امتیاز سوال در گرو کمک به اهداف اوست!
ورودی
در سطر اول $j$ تعداد کارها می‌آید و در سطر بعد $j$ عدد صحیح می‌آید که عدد $i$ام $h_i$ نشانگر سختی کار شماره $i$ است.
در سطر سوم $n$ تعداد افراد می‌آید و در سطر بعد $n$ عدد صحیح با فاصله می‌آید که عدد $i$ام $m_i$ نشانگر حداکثر سختی است که می‌تواند در ماه کار کند.
در سطر $i$ام از $j$ سطر بعد $n$ عدد صحیح می‌آید که عدد $j$ام $s_{i,j}$ نشانگر توانایی فرد $j$ در کار $i$ است. $$1 \le j, h_i, n, m_i, s_{i, j} \le 100$$ تضمین می‌شود که شکلی از تقسیم کار وجود دارد که تمامی کارها کامل انجام شود و هیچ فرد بیش از حداکثر ظرفیتش کار نکند.
خروجی
تنها یک عدد که نشانگر کمینه مجموع ساعات کاری افراد برای انجام تمام کارها است را خروجی دهید. پاسخ شما زمانی درست در نظر گرفته خواهد شد که اختلاف آن با پاسخ واقعی حداکثر $10^{-6}$ باشد.
مثال
ورودی نمونه ۱
1
10
2
6 7
4 1
خروجی نمونه ۱
5.5
ورودی نمونه ۲
3
7 9 11
2
10 17
5 4
8 5
3 2
خروجی نمونه ۲
7.3833333333333
در مثال اول، چنانچه نفر اول $\frac{3}{5}$ کار را انجام دهد و نفر دوم $\frac{2}{5}$ کار را، به ترتیب باید ۱.۵ و ۴ ساعت زمان صرف کنند. توجه کنید که نفر اول با انجام $\frac{3}{5}$ کار متحمل ۶ سختی می‌شود و بیش از این نمی‌تواند کار کند.
در مثال دوم، نفر اول کافی است که همه ۱۰ ظرفیت سختی رو خود را برای کار سوم بگذارد و بقیه کارها را به نفر دوم بسپارد.
ارسال پاسخ برای این سؤال