P1489 Cat–Dog Showdown

In the new season of the Cat–Dog showdown, the competition is decided through the classic game SC (StarCraft). The archrivals Wildcat and Flying Dog have prepared for a long time. To make the war more challenging and dramatic, they agreed that both sides can only choose Terran and build only Marines. The match begins. Soon, Wildcat gathers several squads of Marines and launches a probing attack; however, Flying Dog also has quite a few Marines. The forces meet at Flying Dog’s doorstep, and a bloody battle ensues with anguished screams. Since the fight is at Flying Dog’s home base, his reinforcements arrive quickly. Seeing the disadvantage, Wildcat retreats. At that moment, Flying Dog’s forces are not numerous enough to pursue. Because Medics are not allowed, Marines cannot heal. The wounded just have to endure. Now, Wildcat has once again amassed enough forces and decides to launch a second offensive. To deal a heavier blow this time, Wildcat decides to split the current army into two parts to attack from two routes. Since some Marines were wounded in the first battle, the splitting rule aims to balance the two groups as follows: 1. The numbers of Marines in the two parts may differ by at most one. 2. The total HP of each part must be as close as possible. Please write a program that, given the number of Marines Wildcat currently has and the HP of each Marine, computes the total HP of each part after splitting according to the rules above.

The first line contains an integer $n\ (1 \le n \le 200)$, the number of Marines Wildcat currently has. Each of the following $n$ lines contains one integer, the HP of a Marine $(1 \le a_i \le 40)$.

Output one line with two integers: the total HP of each part after splitting. The total HP of the first part must not exceed that of the second part.

To Flying Dog: I have tried to set the Constraints of this problem in line with StarCraft’s rules. If you still insist that a Marine’s attack values make certain HP totals unreachable, or that the game must build SCVs so the number of Marines cannot reach $200$, then I will have no choice but to make the replay of that Cat–Dog showdown public to the world! Translated by ChatGPT 5