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 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 feodorv C 0.02s
02 Robbinb1993 Cpp 0.03s
03 Morass Cpp14 0.04s
04 emrul Cpp 0.05s
05 Siddartha Cpp14 0.07s
06 markII Cpp14 0.07s
07 a_rahman Cpp14 0.07s
08 SakibAlamin Cpp14 0.08s
09 MAHRahat Cpp14 0.08s
10 Masum_ice Cpp14 0.08s
11 umli Cpp14 0.08s
12 hrOarr Cpp14 0.08s
13 Ishrak Cpp14 0.08s
14 MRoy Cpp 0.08s
15 Bruteforcekid Cpp 0.08s
16 Frdhsn Cpp 0.08s
17 killer_knight Cpp 0.09s
18 Ehsanul_Fahad Cpp 0.09s
19 twyu0721 Cpp 0.09s
20 souravahmed C 0.09s
21 prodipdatta7 Cpp 0.09s
22 tariqiitju Cpp14 0.10s
23 Jubayer_Hasan Cpp14 0.10s
24 smriad Cpp14 0.10s
25 traveller42 Cpp 0.10s
26 anik_JU Cpp14 0.10s
27 subhashis_cse Cpp 0.10s
28 khmahbub20 Cpp 0.10s
29 pulak_ict_mbstu Cpp 0.10s
30 Naim_BSMRSTU Cpp14 0.10s
31 SbrTa Cpp14 0.10s
32 Pure_Protea Cpp14 0.11s
33 wayne6172 Cpp 0.11s
34 ehsan_sshuvo Cpp 0.11s
35 Sarwar05 Cpp 0.11s
36 Jisancse Cpp 0.11s
37 Dark_Ocean Cpp14 0.11s
38 sb_rithu Cpp14 0.11s
39 rithu Cpp14 0.11s
40 sakib_muhit Cpp14 0.11s
41 ash12 Cpp14 0.12s
42 abdulmukit Cpp 0.12s
43 1504038_arafath Cpp 0.13s
44 shameemreza Cpp 0.13s
45 ahoteshanul Cpp 0.13s
46 rabbicse Cpp 0.13s
47 Azaxdev Cpp 0.13s
48 kpretomazi Cpp 0.13s
49 Shajib Cpp 0.13s
50 rashedul007 Cpp 0.13s

Your feedback is our precious!

Or call +88 02 9853138 for support