Korniki [B] - المسألة

#10648. Korniki [B]

الإحصائيات

تم استخدام هذه المسألة في المسابقات التالية:

Potyczki Algorytmiczne 2012, Runda 6

两只虫子决定吃掉一堵老旧的木栅栏。这堵栅栏由 $n$ 根木板组成，每根木板的高度不一定相同。虫子们从身边的白蚁朋友那里听说，有点良性的竞争会让进餐更加愉快。于是，它们决定玩个游戏，轮流吃掉木板。每轮中，轮到的虫子可以吃掉栅栏最边上的一根木板，或者同时吃掉两根最边上的木板。已知每只虫子都会尽可能让自己吃到的木板高度之和最大，请你计算最终每只虫子能吃到多少木头。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 1,000,000$），表示栅栏的木板数。第二行包含 $n$ 个整数 $h_{i}$（$1 \le h_{i} \le 1,000,000,000$），依次表示每根木板的高度。

输出格式

输出一行，包含两个整数。第一个整数表示率先开始游戏的虫子吃到的木板总高度，第二个整数表示它的对手吃到的木板总高度。

样例

输入

4
5 2 9 3

输出

14 5

说明

第一只虫子在第一步可以选择吃高度为 5 的木板、高度为 3 的木板，或者两根都吃。最优策略是只吃高度为 5 的木板。此时，第二只虫子会吃掉高度为 2 和 3 的两根木板。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0