Problem
جک خوش تیپ می خواهد کارخانه های فرآوری اریدیوم خود را راه اندازی کند.
n کارخانه تحت کنترل جک وجود دارد که هر کدام از 1 تا n شماره گذاری شده اند. هر گیاه در کانسار اریدیوم قرار دارد، جایی که به صورت ترکیبی استخراج می شود. و هر چه عدد کارخانه بالاتر باشد، جدیدتر است.
هر کارخانه دارای شاخص کارایی است
i. می تواند مثبت، منفی یا صفر باشد.
هر کارخانه باید سنگ معدن اریدیوم را پردازش کند. می توانید از ذخایر خود استفاده کنید یا سنگ معدنی را که در گذشته توسط کارخانه دیگری فرآوری شده است، از طریق خط لوله بردارید. با این حال، این روند تا حدودی محدود است. اولاً، برای اینکه سیستم خط لوله بیش از حد بارگذاری نشود، هر کارخانه می تواند سنگ معدن را برای فرآوری بیشتر به طور دقیق از یکدیگر بپذیرد (یا از ذخایر خود استفاده نکند). ثانیاً، کارخانه‌های قدیمی‌تر از نظر فنی قادر به بازفرآوری سنگ معدن پس از کارخانه جدیدتر نیستند.
عملکرد نهایی کل سیستم به صورت زیر محاسبه می شود: برای هر کارخانه، بازده آن a
i گرفته می شود و در مرحله فرآوری ضرب می شود که به عنوان تعداد دفعاتی که سنگ معدن ورودی فرآوری می شود محاسبه می شود. (برای جزئیات بیشتر به توضیحات مثال ها مراجعه کنید)، سپس تمام مقادیر به دست آمده برای همه گیاهان خلاصه می شود.
به جک خوشتیپ کمک کنید تا سیستم را سازماندهی کند تا عملکرد کلی کل سیستم تا حد امکان بالا باشد.
ورودی:
خط اول شامل یک عدد طبیعی n است (1 <= n <= 7) - تعداد کارخانه ها.
خط دوم شامل n عدد صحیح جدا شده با فاصله است، که در آن عدد i a
i است (-1000 <= a
i <= 1000) - بازده پایه گیاه تحت شماره i.
خروجی:
چاپ یک عدد - حداکثر عملکرد کل کل سیستم.
مثال:
<بدن>
| ورودی |
خروجی |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
توضیحات:
در مثال اول، برای کارخانه اول بیشترین سود را دارد که سنگ معدن خود را استخراج کند، کارخانه دوم سنگ معدن را از اولی دریافت کند و سومی را از دومی دریافت کند. در این حالت کارخانه اول فرآوری اولیه را انجام می دهد و بهره وری آن 1 * 1 = 1 است. کارخانه دوم فرآوری ثانویه را انجام می دهد ، بهره وری آن 5 * 2 = 10 است و کارخانه سوم سنگ معدن دریافتی را برای بار سوم فرآوری می کند ، بنابراین بهره وری آن 3 * 3 = 9 است. عملکرد کل 1 + 10 + 9 = 20 است.
لطفاً توجه داشته باشید که در این مثال، گیاهان دوم و سوم قابل تعویض نیستند، زیرا کارخانه دوم به دلایل فنی نمی تواند سنگ معدن را پس از سومین فرآوری کند، زیرا از کارخانه سوم قدیمی تر است.
در مثال دوم، کارخانه های اول و سوم از ذخایر خود استفاده می کنند و کارخانه دوم از کارخانه اول سنگ معدن دریافت می کند.