oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

robbery Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

robbery.html

Problem Description

What are you guys playing?
I’m supposed to be playing Game Of War™ but this one player keeps kicking my ass.
Is it TheLegend27?!
Yeah, TheLegend27.
Who is the legend 27?
Some say TheLegend27 is the first Game Of War™ player ever.
Born from fire.

TheLegend27 Backstory

TheLegend27 has robbed the bank with TheJianzhi22, obtaining N banknotes with values Ai . They want to split the money equally among themselves, such that the least amount of money is left behind.

They gambled the money which cannot be split, and managed to double the amount of money obtained! They then proceed to split the doubled money equally.

TheLegend27 only good at playing Game of War™ and has asked TheJianzhi22 calculate the amount of money each person obtains. Help TheJianzhi22 before he too gets destroyed by TheLegend27!

Limits

All variables are positive integers.

Subtask 1 (11%): N ≤ 13, Total value of banknotes ≤ 100000.

Subtask 2 (28%): N ≤ 50, Total value of banknotes ≤ 1000.

Subtask 3 (61%): N ≤ 500, Total value of banknotes ≤ 100000.

Subtask 4 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The next N lines of input will contain 1 integer each, representing Ai.

Output

Output the amount of money each person obtains.

Sample Testcase 1

Input

4
2
3
1
6

Output

6

Explanation

TheLegend27 takes banknotes with values {2, 3, 1} and TheJianzhi22 takes banknotes with value(s) {6}.

Sample Testcase 2

Input

5
2
3
5
8
13

Output

18

Explanation

TheLegend27 takes banknotes with values {5, 8} and TheJianzhi22 takes banknotes with value(s) {13}. The rest of the banknotes is doubled, so they both get {2, 3}.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
111121s256MBMinimum
22861s256MBMinimum
36181s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o robbery -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.