SQRT Cup 2025 - Vòng loại thứ hai - Bảng

Xem dạng PDF

Gửi bài giải

Điểm: 0,00 (OI)
Giới hạn thời gian: 4.0s
Giới hạn bộ nhớ: 512M
Input: BOARD.INP
Output: BOARD.OUT

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bảng kích thước ~n \times m~: có ~n~ hàng và ~m~ cột. Ta gọi giá trị của ô nằm trên hàng ~x~ ~(1 \leq x \leq n)~ và cột ~y~ ~(1 \leq y \leq m)~ là ~a_{x,\ y}~.

Bạn được phép chọn một số ô với quy tắc: Nếu ô ~(p,\ q)~ được chọn thì các ô ~(p - 1,\ q)~ và ~(p,\ q - 1)~ (nếu tồn tại trong bảng) sẽ không thể được chọn nữa. Hay nói cách khác: không được chọn hai ô mà có một ô nằm ngay bên trên hoặc bên trái ô còn lại.

Hãy tìm ra cách chọn sao cho tổng giá trị của các ô được chọn là lớn nhất có thể.

Dữ liệu - Nhập từ tệp văn bản BOARD.inp:

  • Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \times m \leq 400)~.
  • ~n~ dòng tiếp theo mỗi dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2},... , a_{i, m}~ ~(|a_{i, j}| \leq 10^9)~.

Kết quả - Ghi ra tệp văn bản BOARD.out:

  • Gồm một dòng duy nhất chứa kết quả bài toán.

Chấm điểm

Điểm Ràng buộc bổ sung
~36~ ~n = 1~
~26~ ~n \times m \leq 20~
~22~ ~n \le 10~
~16~ Không có ràng buộc gì thêm

Ví dụ

Dữ liệu (BOARD.inp)
3 4
1 2 3 4
3 1 4 2
2 3 1 4
Kết quả (BOARD.out)
20
Giải thích
  • Ta chọn các ô ~(1, 2)~, ~(1, 4)~, ~(2, 1)~, ~(2, 3)~, ~(3, 2)~ và ~(3, 4)~, khi đó kết quả là ~2 + 4 + 3 + 4 + 3 + 4 = 20~.
Dữ liệu (BOARD.inp)
4 5
-7 -6 10 -6 -2
9 -3 -7 8 9
-8 -5 -9 -2 -1
-3 4 -4 -2 -6
Kết quả (BOARD.out)
32
Dữ liệu (BOARD.inp)
1 7
7 7 1 1 8 15 3
Kết quả (BOARD.out)
23

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.