A9097 Boredom

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    // cnt[v] = 值为 v 的元素个数
    vector<int> cnt(mx + 2, 0);
    for (int x : a) cnt[x]++;

    // dp[v] = 只考虑取值 <= v 的元素时，最多能拿到的分数
    vector<int> dp(mx + 2, 0);
    for (int v = 1; v <= mx; v++) {
        // 选 v：cnt[v]*v 分，但此时不能再选 v-1，只能从 v-2 继承
        int take = v * cnt[v] + dp[v - 2 >= 0 ? v - 2 : 0];
        // 不选 v：继承 dp[v-1]
        dp[v] = max(dp[v - 1], take);
    }

    cout << dp[mx] << '\n';
    return 0;
}