SQRT Cup 2025 - Vòng loại thứ hai - Bảng
Xem dạng PDF
Gửi bài giải
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, Scratch, Sed, Swift, TCL, Turing, VB, Zig
Điểm:
800 (OI)
Giới hạn thời gian:
4.0s
Giới hạn bộ nhớ:
512M
Input:
BOARD.inp
Output:
BOARD.out
Dạng bài
Ngôn ngữ cho phép
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) sẽ không được chọn nữa. 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}~ ~(0 \leq |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