[AOJ] No. 0567 最高のピザ (Best Pizza)

2019年11月19日

問題

方針

トッピングを \( k \) 個乗せた時の \( 1 \) ドルあたりのカロリー数を \( f_k \) とし、\( k \) 個のトッピングのカロリーの総和を \( s_k \) とすると、

\[ f_k = \lfloor \dfrac{C + s_k}{A + kB} \rfloor \]

となります。ここで、

\[s_k = \sum_{i = 1}^{k} D_i\]

となるので、\( D_i \) を降順に並べて、\( f_k \) の値を計算します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    ll A, B, C;
    cin >> N >> A >> B >> C;
    vector<ll> D(N);
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }
    sort(D.begin(), D.end(), greater<ll>());
    ll ans = 0;
    ll s = 0;
    for (int i = 0; i < N; i++) {
        s += D[i];
        ans = max(ans, (C + s) / (A + (i + 1) * B));
    }
    cout << ans << "\n";
    return 0;
}