DCP-6: Thief of deVillage!!! Back to All Problems

Easy Divide and Conquer > Dynamic Programming

In a reputed company our team has been working on a game project named **‘Thief of deVillage!!!’**. Sounds thrilling huh! ;-). The game is very simple. You just have to roam around the treasure pyramids of deVillage and steal the treasures buried there for centuries!! ![pyramid][1] As you can see in the figure above that this pyramid of deVillage contains four floors with some cells inside them. The number of cells in a floor = the number of cells in its upper floor + 1. All the cells are full of plenty of gold coins, **C**. Your goal in this game is to grab the maximum possible coins m from these mysterious pyramids. As these pyramids are very special so your journey through them will also be very special. You have to begin your journey from the top cell of the top floor of a pyramid and finish it at any of the bottom cells of the bottom floor. **Game Instructions:** There are only two buttons in this game - the left move button and the right move button. From any position (cell), pressing the left move button will move you to your lower left cell and pressing the right move button will move you to your lower right cell. Remember that you can never go back to the upper floors while moving. You can only choose between going left or right lower cells. As you move from cell to cell the coins at each cell will be deposited to your account. You have to obtain the maximum possible balance from each pyramid to achieve 3 stars (***) on each stage of the game. Now you need to calculate the maximum possible balance **m** for a stage. Input: ------ Each test case starts with a single integer **N (1 ≤ N ≤ 100)** which represents the number of floors in a pyramid. Then there will be N Lines denoting the floor of the pyramid from top to bottom. Each line will contain some integer values separating by spaces representing the number of coins, **C (1 c 100)** in each cell of the respective floor. Two successive cases are separated by a single new line. Output: ------- For each test case, print **“Output: m”** (without quotation) where **m** denotes the maximum possible account balance one can make in a stage. Sample Input ------------ 4 3 21 23 05 13 15 02 18 09 04 5 92 31 72 85 31 21 25 90 22 08 30 50 54 86 88 Sample Output ------------- Output: 57 Output: 352 **Explanation of First Test Case:** *Please look at the given figure in this problem.* *3 + 23 + 13 + 18 = 57* [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/1449455f-fc57-c68b-1be6-08d2e1538f41_a45c2c3af6374e55b0be433dca3046a2_W650xH414.png

Problem Setter:

Md. Azizur Rahman Faiem

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C/C++ 1.00
Java 2.00
C# 2.00
PHP 2.00

Problem Stats




# User Language Timing
01 markII Cpp 0.07s
02 a_rahman Cpp 0.07s
03 Siddartha Cpp 0.07s
04 Dragon_162 Cpp 0.08s
05 ProMAGFAT Cpp 0.08s
06 Ishrak Cpp 0.08s
07 mahrahat Cpp 0.08s
08 Masum_ice Cpp 0.08s
09 umli Cpp 0.08s
10 smriad Cpp 0.10s
11 tariqiitju Cpp 0.10s
12 Jubayer_Hasan Cpp 0.10s
13 sakib_muhit Cpp 0.11s
14 Dark_Ocean Cpp 0.11s
15 ash12 Cpp 0.12s
16 sadia2427 Cpp 0.13s
17 Dinar Cpp 0.16s
18 nazmul_bzs Cpp 0.17s
19 nazmulasha Cpp 0.25s
20 dmehrab06 Cpp 0.36s
21 ih_hira Cpp 0.38s
22 froghramar Cpp 0.46s
23 njrafi Cpp 0.48s
24 sazal_dev Cpp 0.48s
25 mahbub07 Cpp 0.49s
26 anowar1112 Cpp 0.55s
27 Alim14 Cpp 0.56s
28 rayhan50001 Cpp 0.57s
29 KIRIN_36 Cpp 0.58s
30 haasib Cpp 0.65s
31 murad_al_wajed Cpp 0.69s

Your feedback is our precious!

Or call +88 02 9853138 for support