SOLVE

LATER

Elves and Dwarves on War

Problem

Editorial

Analytics

Elves and Dwarves are on war. Elves planted bombs on some of the Dwarves’ villages (Atmost one bomb in one village). But the bombs are not placed very strategically and can cancel each other’s effect. You are the leader of Elves’ army and have to decide which bomb to detonate in order to maximize the damage.

Each bomb has an associated range and damage. If **A[1], A[2] ….. A[n]** are Dwarves’ villages. Then detonating bomb placed at **Ai** with range **R** and Damage **D** causes damage **D** in village **A[i]**, **D-1** in village **A[i+1]**, **D-2** in village **A[i+2] ….. 2** in village **A[i+R-2]** and **1** in village **A[i+R-1]**.

There is one more phenomenon observed when detonating a bomb. Each bomb is of a particular type. If a bomb of type **T** placed at village **A[i]** is detonated, then all the bombs of type other than **T** in its range will be defused. Any bomb of type **T** in the range of bomb at **A[i]** if detonated will block the damage due to bomb at **A[i]** to propagate.

e.g. Bomb placed at 1(Damage 10,Range 6) and Bomb placed at 3(Damage 15,Range 2) are detonated, then for 6 villages

Damage at village 1 -> 10 (Due to bomb at 1)

Damage at village 2 -> 9 (Due to bomb at 1)

Damage at village 3 -> 15(Due to bomb at 3)

Damage at village 4 -> 14(Due to bomb at 3)

Damage at village 5 -> 0

Damage at village 6 -> 0

If only bomb at 1 is detonated and bomb at 3 is not detonated then

Damage at village 1 -> 10 (Due to bomb at 1)

Damage at village 2 -> 9 (Due to bomb at 1)

Damage at village 3 -> 8(Due to bomb at 1)

Damage at village 4 -> 7(Due to bomb at 1)

Damage at village 5 -> 6(Due to bomb at 1)

Damage at village 6 -> 5(Due to bomb at 1)

**NOTE** : All the bombs should be detonated at once (Not sequentially).
Determine the total damage possible.

**Input :**

First line contains **tc**, the number of test cases.

First line of each test case contains **n**, the number of villages.

Next line contains n integers **D[1],D[2]…D[n], D[i]** denotes the damage value of bomb placed at village **i**. If there is no bomb at village **i , D[i]** equals **0**.

Next line contains n integers **T[1],T[2]…T[n], T[i]** denotes the type of bomb placed at village **i**. If there is no bomb at village **i** , **T[i]** equals **-1**.

Next line contains **n** integers **R[1],R[2]…R[n], R[i]** denotes the range of bomb placed at village **i**. If there is no bomb at village **i , R[i]** equals **0**.

**Output:**

For each test case, print a single integer, the maximum total damage value possible.

**Constraints:**

1 <=**tc** <= 10

1 <= **n** <= 100000

1<= **D[i]** <= 1000

1<= **R[i]** <= 10

1 <= **T[i]<= n** (**T[i]**=-1 in case of no bomb)

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

Explanation

In the second test case - There would be no damage to village 1. Detonating the bomb at **village 2** (**damage = 5**, range = 4) would defuse bomb at **village 3** (type = 2) and cause a **damage = 4** to it. Further bomb at **village 4** (**damage = 7**, range = 1)would stop propagation of damage from bomb at village 2. No damage would be caused to village 5 (damage = 0) and at **village 6**, **damage = 6** due to its own. Thus total damage = 5 + 4 + 7 + 6 = 22

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"df23e64": "/pagelets/show-submission/algorithm/elves-and-dwarves-on-war/", "d98daed": "/pagelets/suggested-problems/algorithm/elves-and-dwarves-on-war/", "7de2523": "/pagelets/problems-hint/algorithm/elves-and-dwarves-on-war/", "1920163": "/pagelets/recommended-problems/algorithm/elves-and-dwarves-on-war/", "1e6d6b6": "/pagelets/problem-author-tester/algorithm/elves-and-dwarves-on-war/"}

realtime.hackerearth.com

80

fce78cf8999eca367a87e54e6eb4f983c14ebee6

58a29e5cae2309f04b28

/realtime/pusher/auth/