가장 긴 증가하는 부분 수열 K

증가하는 부분 수열 중 길이가 최대인 것들을 인덱스 순서의 사전순으로 나열했을 때 K번째 수열을 구하고, K개 미만이면 -1을 출력한다.

어려움8동적 계획법이분 탐색그리디조합론아직 제출이 없습니다시간 제한0.25초메모리 제한512 MB

문제 설명

예제8

N개의 정수로 이루어진 수열 A1, A2, ..., AN에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 L이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, K번째 오는 수열을 구해보자.

두 LIS Ai1, Ai2, ..., AiL와 Aj1, Aj2, ..., AjL이 있을 때, ik ≠ jk를 만족하는 k가 하나라도 존재하면 다른 LIS이다.

첫째 줄에 N과 K가 주어진다. 둘째 줄에 공백으로 구분된 A1, A2, ..., AN이 주어진다.

K번째 LIS를 공백으로 구분해서 출력한다. K번째 LIS가 없을 때는 -1을 출력한다.