#P1018. 小核桃与数组规则

小核桃与数组规则

题目描述

小核桃身处在一个神秘的逃生游戏中,他需要通过解决各种谜题来获得能够帮助他逃脱的物品。在一道谜题中,小核桃被赋予了一个整数数组和一组规则,让他按顺序进行操作。以下是给小核桃的指示:给定一个整数数组,请按以下方法计算得分最高的方案:

  • 首先选择一个整数vv并删除数组中所有等于vv的元素,并将它们的总和加入积分中。
  • 同时,删除数组中所有等于v+1v+1v1v-1的元素,这些元素不得分。

重复上述步骤,直到数组中没有更多的元素为止。 现在,小核桃需要计算按照这些规则可以获得的最大分数是多少?

输入描述

第一行包含一个整数nn,表示有nn个整数。

第二行包含nn个整数,表示第ii个数字值为aia_i,之间以一个空格隔开。

输出描述

计算出小核桃按照规则可以获得的最大分数。

5
5 6 6 4 11
27

样例说明:

首先删除1111获得1111分,同时10和12不存在,[5,6,6,4,11]>[5,6,6,4][5,6,6,4,11] -> [5,6,6,4] 。 删除66获得62=126*2=12分,同时删除5,[5,6,6,4,11]>[4][5,6,6,4,11] -> [4] 。 最后删除44获得44分,总分为11+12+4=2711 + 12 + 4 = 27

数据范围

每组数据点1010分,共1010组数据。

数据点编号 nn的范围 aia_i的范围
11 1n1031 \leq n \leq 10^3 0ai1030 \leq a_i \leq 10^3(保证每个aia_i独一无二)
22~55 0ai1030 \leq a_i \leq 10^3
66~1010 1n1061 \leq n \leq 10^6 0ai1060 \leq a_i \leq 10^6