Đường đi có tổng lớn nhất

View as PDF

Submit solution


Points: 0.05 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bảng ~A~ kích thước ~m \times n~ ~(1 \le m~, ~n \le 100)~, trên đó ghi các số nguyên ~a_{ij}~ ~(|a_{ij}| \le 100)~. Một người xuất phát tại ô nào đó của cột ~1~, cần sang cột ~n~ (tại ô nào cũng được).

Quy tắc đi: Từ ô ~(i, j)~ chỉ được quyền sang một trong ~3~ ô ~(i, j + 1)~; ~(i - 1, j + 1)~; ~(i + 1, j + 1)~

Input

Dòng ~1~: Ghi hai số ~m~, ~n~ là số hàng và số cột của bảng.

~M~ dòng tiếp theo, dòng thứ ~i~ ghi đủ ~n~ số trên hàng ~i~ của bảng theo đúng thứ tự từ trái qua phải

Output

Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

Sample Input

5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Sample Output

41

Comments

Please read the guidelines before commenting.



  • -10
    ksomg   commented on Jan. 4, 2022, 11:10 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -21
    DoanTungLamKoCopyCode   commented on Oct. 31, 2021, 8:57 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 4
    mikamikaela   commented on Aug. 3, 2021, 2:40 p.m.

    Tác giả cho em hỏi có thực sự là (-100 <= A[i][j] <= 100) với mọi i, j không tác giả ơi.

    Vì em để MIN là -(1e9+7) thì AC, còn để MIN là -107 thì tạch :V


    • 15
      ngfam   commented on Aug. 3, 2021, 10:10 p.m.

      ~ abs(A[i][j]) \leq 100 ~ thì tổng đường đi có thể xuống ~-100 \times M~ nhé.


      • 2
        mikamikaela   commented on Aug. 5, 2021, 10:32 p.m.

        em để MIN mà MIN của 1 cell cơ


        • 0
          jalsol   commented on Aug. 6, 2021, 6:45 a.m.

          1 cell trong mảng dp sẽ là tổng của cả đường đi, nên min của cell đó nên là min của tổng sẽ hợp lý hơn


  • -104
    dungp24   commented on May 30, 2021, 11:11 a.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.