https://atcoder.jp/contests/abc441/tasks/abc441_c
問題が読み取りにくくてずっと誤解していたのですが、よくよく読んだらわかりました。これはどのカップに何mリットル入っているかはわかるので、上から選べばいいんですね。
Rでまとめて処理したら速くなるので、そうなるようにします。まず、Aを降順にソートしてBにします。それから最悪水が入っている分を除いてCにします。そして、大きいほうから足していけばいいので、累積和を求めます。累積和で最初にX以上になる場所を探せばいいですが、これもwhichでまとめて処理します。これでTRUEになるインデックスのvectorを得ます。これの最初が求める場所で、これに水の分のN-Kを足します。
v <- scan("stdin", numeric()) N <- as.integer(v[1]) K <- as.integer(v[2]) X <- v[3] A <- v[4:(N+3)] B <- sort(A, decreasing=TRUE) C <- B[(N-K+1):N] acc <- cumsum(C) indices <- which(acc >= X) if(length(indices) > 0) { result <- N - K + indices[1] } else { result <- -1 } cat(result, "\n")
