#D. 蒜头君的奖励

    传统题 1000ms 256MiB

蒜头君的奖励

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

为了奖励蒜头君在七月模拟赛普及组中取得优异成绩,老师准备给他一个奖励。 他面前有一个包含奖励值的数组。蒜头君最初的总奖励值为0,每个奖励值都有一个对应的下标,所有下标都是未标记的。蒜头君可以执行一下操作任意次:

1.从区间[0,n-1]中选择一个未标记的下标i。

2.如果aia_{i}大于等于当前的总奖励值x,则将aia_{i}加到x上,并标记下标i。

你可以帮蒜头君计算出他可以获得的奖励值最大是多少嘛?

输入格式

第一行输入一个整数n,表示数组大小。 第二行输入n个整数,表示奖励值数组。

输出格式

输出一个整数,表示蒜头君可以获得的最高奖励值。

数据范围

对于40%的数据,n10,ai2000n\leq10,a_{i}\leq2000;

对于100%的数据,n2000,ai2000n\leq2000,a_{i}\leq2000;

样例

4
1 2 4 7
14
样例解释1

第一次选择1,此时121\leq2,选择2,此时242\leq4,选择4,此时777\leq7,选择7,大小为14。

2
7 2
9
样例解释2

第一次选择2,此时2$\leq$7,选择7,总和是9

3
4 3 6
10
样例解释3

第一次选择4,此时4$\leq$6,总和是10。

时间空间限制

1000ms,262144K

8.5模拟测试

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-8-5 17:00
结束于
2024-8-5 17:09
持续时间
0.2 小时
主持人
参赛人数
27