問題一覧 > 通常問題

No.549 Material Synthesis System

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 266
作問者 : nanae / テスター : はむこ
お気に入りにしたユーザー ProblemId : 1617 / 自分の提出
問題文最終更新日: 2026-06-25 04:44:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 170 (順位表) の他の問題:

Problem Statement

You are playing a social game called Yukicoder's Gate.
Yukicoder's Gate is an RPG in which you raise multiple androids.
You currently own $N$ androids, and their experience points are $x_1, x_2, \dots, x_N$, respectively.
You want to combine these $N$ androids into one android using the synthesis system.
The details of the synthesis system are as follows.

  • Let $a$ be the experience points of the material android, and $b$ be the experience points of the android being synthesized into
  • The value of half of the material android's experience points, rounded down, is added to the experience points of the android being synthesized into
  • That is, as a result of the synthesis, the experience points of the android being synthesized into become $b + \left \lfloor \frac{a}{2} \right \rfloor$
  • The material android disappears
You want to make the experience points of the one android remaining at the end as large as possible.
Find the maximum possible value of the experience points of the one android remaining at the end.

Input

$N$
$x_1$ $x_2$ ... $x_N$

The first line contains the number $N$ of androids you own.
The second line contains the experience points $x_i$ of each android, separated by single-byte spaces.

The constraints are as follows.

  • $2 \leq N \leq 10^5$
  • $1 \leq x_i \leq 10^4$
  • All input values are integers

Output

Output the maximum possible value of the experience points of the one android remaining at the end.

Print a newline at the end.

Sample

Sample 1
Input
3
1 2 3
Output
4

In this case, performing the synthesis in the following order leaves an android with 4 experience points.

  • Synthesizing android 2 into android 1 makes the experience points of android 1 equal to 2, and android 2 disappears
  • The experience points of the remaining androids are 2, x, 3 (x indicates that the android has disappeared)
  • Synthesizing android 1 into android 3 makes the experience points of android 3 equal to 4, and android 1 disappears
  • The experience points of the remaining androids are x, x, 4, and the synthesis is now complete

Sample 2
Input
5
2 2 2 2 2
Output
6

In this case, repeating "synthesize android $i(>1)$ into android 1" leaves an android with 6 experience points, which is the maximum value.

Sample 3
Input
16
5 48 74 84 94 13 24 15 92 79 74 89 32 30 5 24
Output
435

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。