← 返回题目列表

AtCoder · agc020_c

C. 中位数和

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

你被给予 N 整数 A_1, A_2, ..., A_N.

考虑所有非空子序列的总和 A。有 2^N - 1 这样的总和,是一个奇数。

令这些总和按非降序排列的列表为 S_1, S_2, ..., S_{2^N - 1}.

找到这个列表的中位数, S_{2^{N-1}}.

约束

  • 1 \leq N \leq 2000
  • 1 \leq A_i \leq 2000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_N

输出

打印所有非空子序列之和的排序列表的中位数 A.


示例输入 1

3
1 2 1

示例输出 1

2

在这种情况下, S = (1, 1, 2, 2, 3, 3, 4)。其中位数为 S_4 = 2.


示例输入 2

1
58

示例输出 2

58

在这种情况下, S = (58).