DA-F93-CA4-1
Time Limit: 2 Seconds Memory Limit: 32768 KB
بازی ای به این صورت است که در ابتدا یک آرایه از اعداد صحیح مثبت داریم. بازی دو بازیکن دارد. هر بازیکن نقطه ی شروع مشخصی دارد. بازیکن ها به نوبت حرکت میکنند. در هر حرکت بازیکنی که نوبتش است عدد ی که روی خانه اش نوشته شده است را برمیدارد و عدد صفر را به جای آن می نویسد. سپس به خانه ی چپ یا راست حرکت میکند. منطقا هیچ بازیکنی نمیتواند از آرایه خارج شود. دو بازیکن می توانند همزمان در یک خانه قرار داشته باشند. امتیاز هر بازیکن مجموع اعدادی است که برداشته. بازی زمانی تمام میشود که درکل خانه های آرایه صفر نوشته شده باشد.
به وضوح ابتدا بازیکن اول حرکت میکند. اگر هر دو بازیکن باهوش باشند و بهینه بازی کنند بیشترین امتیازی که هر یک بدست می آورند چقدر است؟ بازی کردن بهینه یعنی هرکس سعی کند امتیاز خودش را بیشتر کند و در صورتی که حالت های مختلفی در این بیشینه کردن وجود داشته باشد حالتی را انتخاب کند که امتیاز حریفش کمتر شود.
Input
در خط اول ورودی عدد طبیعی n تعداد عناصر آرایه داده میشود. n در بازه ی [2,1e5] است
در خط بعد n عدد صحیح نامنفی نوشته میشود که هر عدد کمتر یا مساوی 10000 است.
در خط سوم دو عدد طبیعی نوشته می شود که به ترتیب نقطه ی شروع بازیکن اول و دوم است. خانه های آرایه از یک شماره گذاری شده اند.
Output
امتیاز بازیکن اول و دوم را در یک خط و با یک فاصله میان آنها چاپ کنید با این فرض که هر دو بازیکن بهینه بازی میکنند.
Sample Input
10 1 2 3 4 5 6 7 8 9 0 4 8
Sample Output
21 24Submit