[Usaco2010 Jan]Taking Turns

时间限制：1s 空间限制：64MB

题目描述

Farmer John has invented a new way of feeding his cows. He lays out N (1 <= 3="" 5="" 8="" 9="" 10="" 17="" n="" <="700,000)" hay="" bales="" conveniently="" numbered="" 1..n="" in="" a="" long="" line="" the="" barn.="" bale="" i="" has="" weight="" w_i="" (1="" sequence="" of="" six="" weights="" might="" look="" something="" like:="" pair="" cows="" named="" bessie="" and="" dessie="" walks="" down="" this="" after="" examining="" all="" haybales="" to="" learn="" their="" weights.="" is="" first="" chooser.="" they="" take="" turns="" picking="" eat="" as="" walk="" (once="" haybale="" skipped,="" cannot="" return="" it).="" for="" instance,="" if="" go="" line,="" possible="" scenario="" is:="" *="" picks="" skips="" diagrammatically:="" |="" only="" shows="" single="" skipped="" bale;="" either="" cow="" can="" skip="" many="" she="" pleases="" when="" it's="" her="" turn.each="" wishes="" maximize="" total="" herself="" consumes="" (and="" each="" knows="" that="" other="" goal).furthermore,="" will="" choose="" thatmaximimizes="" consumed.="" given="" weights,="" determine="" amount="" hay.="" 一排数，两个人轮流取数，保证取的位置递增，每个人要使自己取的数的和尽量大，求两个人都在最优策略下取的和各是多少。="" p="">

输入格式

* Line 1: A single integer: N * Lines 2..N+1: Line i+1 contains a single integer: W_i

输出格式

* Line 1: Two space-separated integers, the total weight of hay consumed by Bessie and Dessie respectively

样例输入

样例输出

27 17

提示

没有写明提示

题目来源

Gold