Codeforces Round #664 (Div. 1) 感想

Aだけの1完で、レート変動は 1940→1914 (-26)。

div.1で勝てないFAKEと申します......。今のところ0勝2敗1分です。

A - Boboniu Chats with Du

$a_i > m$ を満たすからかいが発生する回数を固定するとからかえない日数が決まるので最適解が貪欲に求められる。

固定値を動かして大域解を求めればOK。

提出コード

リンク： http://codeforces.com/contest/1394/submission/89719886

void solve() {
    ll N, D, M;
    cin >> N >> D >> M;
    Vl A, B;
    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        if (a > M) {
            A.emplace_back(a);
        }
        else {
            B.emplace_back(a);
        }
    }
    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());
 
    ll na = (ll)A.size();
    ll nb = (ll)B.size();
 
    Vl cuma(na + 1), cumb(nb + 1);
    for (ll i = 0; i < na; i++) {
        cuma[i + 1] = cuma[i] + A[i];
    }
    for (ll i = 0; i < nb; i++) {
        cumb[i + 1] = cumb[i] + B[i];
    }
 
    ll ans = 0;
 
    if (na == 0) {
        ans = cumb[nb];
    }
    else {
        ans = A[0];
        for (ll i = min(na - 1, (N - 1) / (D + 1)); i >= (na + D) / (D + 1) - 1; i--) {
            ll k = (N - 1) - (D + 1) * i;
            if (k < 0) continue;
            if (k > nb) k = nb;
            ll t1 = cuma[i + 1];
            ll t2 = cumb[k];
            ans = max(ans, t1 + t2);
        }
    }
 
    prints()(ans);
}