Tổng cặp thứ K

Binary-search Buổi 13 — Chặt nhị phân đáp án sorting two-pointers
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho hai mảng số nguyên $A$ gồm $N$ phần tử và $B$ gồm $M$ phần tử. Xét tất cả $N \times M$ tổng có dạng $A_i + B_j$ ($1 \le i \le N, 1 \le j \le M$).

Hãy tìm giá trị nhỏ thứ $K$ (đánh số từ $1$) trong $N \times M$ tổng này sau khi sắp xếp không giảm.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, K$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
  • Dòng thứ ba chứa $M$ số nguyên $b_1, b_2, \dots, b_M$.
Dữ liệu ra

In ra tổng nhỏ thứ $K$.

Ví dụ
Input Output
3 3 4

1 7 11 2 4 6 | 9 | | 2 2 3 -5 3 -2 4 | 1 |

Giới hạn
  • $1 \le N, M \le 10^5$
  • $1 \le K \le N \times M$
  • $-10^9 \le a_i, b_j \le 10^9$.
Draft saved