Bài 3. Tìm cặp số (HSG THPT TP. Hải Phòng 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT TP. Hải Phòng 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho số nguyên dương ~S~ và ma trận ~A~ có ~m~ hàng, ~n~ cột. Ô giao giữa hàng ~i (i = 1 \ldots m)~ và cột ~j (j = 1 \ldots n)~ có số nguyên dương ~a_{ij} (a_{ij} \le 10^9)~.

Tìm tổng lớn nhất của 2 phần tử ở 2 vị trí khác nhau trong ma trận ~A~ sao cho tổng này không lớn hơn số nguyên dương ~S~. Nếu không tìm được 2 phần tử theo yêu cầu thì in ra −1.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa 3 số nguyên dương ~m, n, S (m, n \le 10^3; S \le 2 \times 10^9)~.
  • ~m~ dòng tiếp theo, mỗi dòng có ~n~ số nguyên dương không vượt quá ~10^9~.

Kết quả

Một dòng duy nhất là tổng lớn nhất tìm được theo yêu cầu. Nếu không tìm được thì in ra −1.

Ví dụ

Input 1

1 4 17
1 9 7 11

Output 1

16

Input 2

2 4 7
1 2 2 3
3 3 7 2

Output 2

6

Input 3

3 4 10
6 7 8 9
5 6 7 8
9 8 8 7

Output 3

-1

Ràng buộc

  • Subtask 1 (20% số điểm): ~m = 1~.
  • Subtask 2 (30% số điểm): ~m, n \le 10^2~.
  • Subtask 3 (50% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...