Codeforces 455A. Boredom

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.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define SIZE 100005
struct node
{
    LL val;
    LL nums;
} nod[SIZE];

LL f[SIZE][2];
LL res = 0,n;

int main(){
    //freopen("test.in","r",stdin);
    cin >> n;
    for (int i=0;i<=100000;++i){
        nod[i].val = i;
        nod[i].nums = 0;        
    }
    for (int i=1;i<=n;++i){
        int tmp;
        cin >> tmp;
        nod[tmp].nums ++;
    }

    memset(f,0,sizeof(f));
    LL temp = -1;
    for (int i=1;i<=100000;++i){
        f[i][1] = f[i-1][0] + i * nod[i].nums;
        temp = max(temp,f[i-1][1]);
        f[i][0] = temp;
    }

    // for (int i=1;i<=5;i++){
    //     cout << i << " " << f[i][1] << " " << f[i][0] << endl;
    // }

    cout << max(f[100000][1],f[100000][0]);
    return 0;    
}

View Code

好久没做题了，各种错。。

果然这类题的直接Long long就是了