Editorial for KTHSUM

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Nguồn: Free Contest

Subtask 1

Vì $n \le 1000$ ~n \le 1000~ nên ta có thể sinh toàn bộ $n^2$ ~n^2~ phần tử của dãy $D$ ~D~, sắp xếp theo thứ tự không giảm rồi in ra $k$ ~k~ phần tử đầu.

Độ phức tạp: $O(n^2.log(n^2))$ ~O(n^2.log(n^2))~

Subtask 2

Thay vì sinh toàn bộ $n^2$ ~n^2~ phần tử, ta chỉ sinh $k$ ~k~ phần tử nhỏ nhất của dãy $D$ ~D~ bằng cách sử dụng heap hoặc set như sau:

Sắp xếp dãy B theo thứ tự không giảm.
Với mỗi phần tử $a_i$ ~a_i~ của dãy $A$ ~A~, thêm vào heap/set cặp phần tử $(a_i, b_1)$ ~(a_i, b_1)~.
Thực hiện thao tác sau $k$ ~k~ lần: Lấy ra cặp phần tử $(a_i, b_j)$ ~(a_i, b_j)~ có tổng nhỏ nhất từ heap/set và in ra tổng đó. Thêm vào heap/set cặp phần tử $(a_i, b_{j+1})$ ~(a_i, b_{j+1})~ nếu $j < n$ ~j < n~.

Độ phức tạp: $O((n + k).log(n))$ ~O((n + k).log(n))~