DCP-218: Pacman Back to All Problems

Medium Divide and Conquer > Dynamic Programming


In this problem, you will be given a 2D matrix with **N** rows and **M** columns. There is a Pacman in the (1,1) position. He can move only to right or only to down. Each cell of the matrix contains some coin values. If Pacman moves to a cell then he earns that amount of coin value that the cell contains. Your task is to calculate the maximum number of coins the Pacman can earn if he wants to reach to the cell (N,M). Input: ------ First line of input contains an integer **T** that denotes the number of test cases **(T<=100)**. Next line contains two integers **N** and **M** separated by space **(1 <= N,M <=100)**. Next N lines contains M integers separated by space which denotes the coin value of that cell. **(coin value <=1000)** Output: ------- For each set of inputs, print a single integer in a single line, the maximum coin values that Pacman can earn Sample Input ------------ 2 5 6 1 6 2 3 4 5 9 1 2 1 8 6 2 5 8 6 10 5 8 5 9 4 2 8 23 5 8 5 9 6 2 3 1 5 3 4 2 6 Sample Output ------------- 76 15


Problem Setter:

Md. Samiul Alam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats

52/86

Solve/Submission

Ranking

# User Language Timing
01 MAHRahat Cpp14 0.02s
02 rayhan50001 Cpp14 0.02s
03 SakibAlamin Cpp14 0.02s
04 vatsalsharma376 Cpp14 0.02s
05 murad_al_wajed Cpp 0.03s
06 Morass Cpp14 0.03s
07 traveller42 Cpp14 0.03s
08 feodorv Cpp14 0.03s
09 nazmul_bzs Cpp14 0.03s
10 sakib_muhit Cpp 0.03s
11 umli Cpp14 0.03s
12 tariqiitju Cpp14 0.03s
13 Masum_ice Cpp14 0.03s
14 Ishrak Cpp14 0.03s
15 ash12 Cpp14 0.03s
16 anowar1112 Cpp14 0.03s
17 haasib Cpp14 0.03s
18 seyedssz Cpp14 0.03s
19 smriad Cpp 0.03s
20 prateepm Cpp14 0.03s
21 Sarwar05 Cpp 0.03s
22 Protap_Ghose Cpp 0.03s
23 mahmud2690 Cpp14 0.04s
24 abdulmukit Cpp 0.04s
25 Robbinb1993 Cpp 0.04s
26 sadia2427 Cpp14 0.04s
27 AbirRahman Cpp 0.06s
28 mh755628 Cpp 0.06s
29 Faizul_BU Cpp14 0.07s
30 Shubhode CSharp 0.12s
31 RandyWaterhouse Python3 0.21s
32 robin_aust Cpp 1.15s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support