Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PT_KT1B2 - Búng chim |
Bạn biết gì về trò chơi “Made in Việt Nam” Flappy Bird của tác giả Nguyễn Hà Đông? Hôm nay, chúng ta làm quen với phiên bản 2 của trò chơi này nhé.
Cho m hàng, mỗi hàng có n trụ đồng, khoảng cách giữa các trụ coi như không đáng kể. Trụ ở hàng i cột j có độ cao hij.
Chú chim Flappy xuất phát ở mặt đất (độ cao bằng 0) và dự trữ W đơn vị năng lượng, mỗi lần nhảy từ ví trí này đến vị trí khác chú bị tiêu hao một năng lượng đúng bằng độ cao của vị trí nhảy tới. Nhiệm vụ của chú chim ở phiên bản này là phải nhảy qua n trụ ở n cột khác nhau, mỗi lần chú chỉ có thể nhảy tới bất kỳ một trụ nào đó của cột kế tiếp.
Bờm và các bạn trong lớp mới tham gia và rất hứng thú với trò chơi này. Để chứng tỏ khả năng không “yếu kém”, Bờm muốn chú chim Flappy của mình nhảy từ trụ này tới trụ khác sao cho độ cao của các trụ không giảm và tổng độ cao các trụ là lớn nhất có thể.
Bạn hãy giúp Bờm chỉ ra hành trình của chú chim Fllapy.
Input
- Dòng đầu chứa ba số n, m, W
- M dòng sau, dòng thứ I+1 (i=1..n), ghi n số hi1, hi2,…, hin.
Output
- Nếu không tồn tại đáp số ghi ra số -1, ngược lại bạn ghi một số nguyên là tổng độ cao lớn nhất của các trụ chú chim Flappy nhảy qua.
Example
Input:2 3 10
2 7 6
4 3 5 Output: 10
Input:2 3 7
7 1 3
2 5 6Output: -1* Giải thích ví dụ 1: (1,1) -> (2,2) -> (2,3)* Chú ý:- 1≤W≤100 000
- 1≤M, N≤ 20
- 1≤Hij≤ 1 000
- 30% số test đầu có 1≤M, N≤ 10
- 30% số test tiếp theo có 1≤M, N≤ 15
- 40% số test cuối có 1≤M, N≤ 20
Được gửi lên bởi: | Vương Trung Hiếu Nghĩa |
Ngày: | 2014-09-16 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | ASM32-GCC MAWK BC C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG DART ELIXIR FANTOM FORTH GRV JULIA KTLN OBJC OCT PAS-FPC PROLOG PYPY3 R RACKET CHICKEN SQLITE SWIFT UNLAMBDA |
Nguồn bài: | Đề Phú Thọ |