명상
면접 대비시간 제한1초메모리 제한512 MB
n개의 운동 점수가 주어질 때, 서로 다른 k개를 골라 합이 최대가 되도록 한다.
문제
Luna는 힘든 하루를 보내서 기분을 풀 명상 루틴을 하려고 한다. Luna의 루틴마다 편안함의 정도가 다르고, 루틴이 얼마나 편안한지 알아내기 위해 Luna는 점수를 계산한다. 점수가 높을수록 더 편안한 루틴이다.
Luna는 n개의 운동 각각에 양의 정수 등급을 매겼고, 루틴의 점수는 그 루틴에 포함된 운동들의 등급을 모두 더한 값이다. Luna가 등급을 매긴 운동 목록을 받아서, 서로 다른 k개의 운동으로 이루어진 루틴의 점수 중 최댓값을 구하시오.
입력
첫째 줄에 공백으로 구분된 두 정수 n과 k가 주어진다. 다음 n개의 줄에 각각 정수 하나가 주어지며, i + 1번째 줄에는 i번째 운동의 등급 gi가 주어진다.
출력
서로 다른 k개의 운동으로 이루어진 루틴의 최대 점수를 정수 하나로 출력한다.
제한
- 1 ≤ k ≤ n ≤ 100 000
- 모든 1 ≤ i ≤ n에 대해 0 ≤ gi ≤ 10 000
힌트
운동 1, 2, 5를 선택하면 총점은 10 + 22 + 10 = 42가 된다.