[일반] D 시간초과남 도움

[익명(106.244)]

밑에 고닉이 올린대로 구현해봤는데 중복값이 거의 없을때 터지넹 ㅜㅜ 테케 9번이었음

pq 에 넣는 시간이 너무 긴거같다

난 앞쪽 dp 값들 싹다 대입해서 뒤로 가면 최대 5백만가지 값이 pq에 들어가는거 같음ㅋㅋ (dp 하나당 k개씩 최대 n개)

어떻게 줄여야함..?

[EN_SA(encludingsalt)]

그걸 pq에 최초엔 꼭대기만 넣고 뽑을때마다 그 다음값을 대신 넣는거임 그럼 pq에는 최대 n개만 관리되고

[EN_SA(encludingsalt)]

근데 이렇게 짠거 같은데 시간초과나는건 그냥 더 궁리해서 깎아보시고

[익명(106.244)]

아 pq 개수도 관리하는거임? 난 걍 한번에 다 때려넣고 k개 뽑았는데ㅋㅋㅋ 생각해보니 dp에도 크기순으로 정렬돼있으니까 그걸 써야되는구나 ㄱㅅㄱㅅ 고민해볼게