首页 > 代码库 > CodeForces - 455A Boredom

CodeForces - 455A Boredom

2024-11-16 05:32:39   203人阅读

Alex doesn‘t like boredom. That‘s why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let‘s denote it ak) and delete it, at that all elements equal to ak?+?1 and ak?-?1 also must be deleted from the sequence. That step brings ak points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input

The first line contains integer n (1?≤?n?≤?105) that shows how many numbers are in Alex‘s sequence.

The second line contains n integers a1, a2, ..., an (1?≤?ai?≤?105).

Output

Print a single integer — the maximum number of points that Alex can earn.

Example

Input
2
1 2
Output
2
Input
3
1 2 3
Output
4
Input
9
1 2 1 3 2 2 2 2 3
Output
10

Note

Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this [2,?2,?2,?2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.

 

维护两个变量，即b（包含上一个的最大值），c（不包含上一个的最大值）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define lld I64d

using namespace std;

long long d[100005];

int main()
{
    long long a=0,b=0,c,x;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&x);
        d[x]+=x;
    }
    for(int i=1;i<=100000;i++)
    {
        c=a+d[i];
        a=max(a,b);
        b=c;
    }
    printf("%lld",max(a,b));
    
    
    return 0;
}

 

CodeForces - 455A Boredom


联系
我们