D. 子集和中位数

    Type: Default 1000ms 256MiB

子集和中位数

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题意

给你 NN 个整数 A1,A2,,ANA_1,A_2,\cdots,A_N

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

我们将这些和按不降的顺序排序得到 S1,S2,,S2N1S_1,S_2,\cdots,S_{2^N-1}

SS 的中位数,即 S2N1S_{2^{N-1}}

输入格式

第一行一个整数 NN

第二行 NN 个整数 A1,A2,,ANA_1,A_2,\cdots,A_N

输出格式

输出一行一个整数,表示 AA 的所有非空子序列的和排序得到的数列的中位数。

输入输出样例 #1

输入 #1

3
1 2 1

输出 #1

2

输入输出样例 #2

输入 #2

1
58

输出 #2

58

数据范围

样例 1 解释

此时 S=(1,1,2,2,3,3,4)S=(1,1,2,2,3,3,4),中位数为 S4=2S_4=2

样例 2 解释

此时 S=(58)S=(58)

限制条件

对于所有的测试点

  • 1N20001\le N\le 2000
  • 1Ai20001\le A_i\le 2000
  • 所有输入均为整数。
测试点编号 NN 特殊性质 分值
1 N20N \le 20 5
2 N2000N \leq 2000 AA 35
3 60

性质 AA,保证 i=1nAi10000\sum_{i=1}^{n} A_i \le 10000

暑假集训模拟赛2

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2025-8-17 14:15
End at
2025-8-17 18:15
Duration
4 hour(s)
Host
Partic.
10