Maximize Profit [CSAcademy #63 B]

https://csacademy.com/contest/round-63/task/maximize-profit/

S円のお金とQ個の確率を持っている。
確率を適切に入れ替えて順番に使っていくことを考える。
i番目の確率を使う場合は2つの選択が選べる。
1. 確率を使ってお金をP[i]%上昇させる
2. 確率を捨ててお金を+K円する
最終的なお金の最大値は？

解法

まず、全て確率を使ってお金を上昇させることを考えてみる。
すると、確率を使う順番は確率が小さいものから順番に使っていくことが良いことが分かる。
なので、適切に確率を入れ替えて使うが、昇順に入れ替えておけばいい。
　
次にお金を+Kすることを考えるが、これは確率で上げる前にやるのが効率がよい。
そのため、前半はお金を+Kして、後半は確率で上げる戦略が最適戦略であると言える。
　
どのタイミングで+Kから確率を使う方に変えるかを全探索して、お金の最大値を答える。
注意点はdouble計算しているつもりがint計算で切り捨てになってしまうのがよくある。

int S, Q, K, P[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> Q >> K;
    rep(i, 0, Q) cin >> P[i];
    sort(P, P + Q);

    double ans = -1;
    rep(i, 0, Q + 1) {
        // [0,i)は+K
        double a = S;
        rep(j, 0, i) a += K;
        rep(j, i, Q) a *= 1.0 * (100 + P[j]) / 100;
        ans = max(ans, a);

    }
    printf("%.10f\n", ans);
}