A93773.相邻数清理

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给定一个长度为 nn 的序列,其中第 ii 个数为 aia_i

你可以进行若干次选择操作:

  • 如果你决定选择某个数值 xx,你会一次性拿走序列中所有等于 xx 的元素,得到的分数为 x×x \times (序列中 xx 出现的次数)。
  • 与此同时,序列中所有等于 x1x-1x+1x+1 的元素会被清空(之后无法再选择它们对应的数值)。

你可以选择若干个不同的数值(每个数值至多选择一次),目标是让最后得到的总分数最大。请输出这个最大分数。

输入格式

第一行一个整数 nn

第二行包含 nn 个整数 a1,a2,,ana_1,a_2,\dots,a_n

输出格式

输出一个整数,表示可以获得的最大总分数。

输入输出样例

  • 输入#1

    5
    1 2 2 3 3
    

    输出#1

    7
    

说明/提示

1n2×1051 \le n \le 2\times10^5

1ai1051 \le a_i \le 10^5

对于样例:

各数出现次数:1111 次,2222 次,3322 次。

  • 选择 22 的话:得分 =2×2=4=2\times2=4,且 1133 不能再选。

  • 选择 1133 的话:得分 =1×1+3×2=7=1\times1 + 3\times2 = 7

    最大为 77

首页