【題解】Codeforces 1395D. Boboniu Chats with Du

【題目敘述】http://codeforces.com/contest/1395/problem/D

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, d, m, a;
long long ans, mx;
vector <int> v, v2;
 
int main() {
    cin >> n >> d >> m;
    for (int i = 1; i <= n; i++){
        cin >> a;
        if (a > m) v.push_back(a);
        else{
            v2.push_back(a);
            ans += a;
        }
    }
    mx = ans;
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    sort(v2.begin(), v2.end());
    reverse(v2.begin(), v2.end());
    int p = v2.size();
    for (int i = 1; i <= v.size(); i++){
        int num = n-1-(d+1)*(i-1);
        if (num < 0) break;
        for (int j = p; j > num; j--){
            ans -= v2[j-1];
        }
        p = min(p, num);
        ans += v[i-1];
        mx = max(mx, ans);
    }
    cout << mx << "\n";
}

分享本文 Share with friends