Tổng cặp thứ K
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Đề 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$.
Community Discussion