All Tracks Algorithms Dynamic Programming Problem

Elves and Dwarves on War
Tag(s):

Medium

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)

SAMPLE INPUT
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
SAMPLE OUTPUT
21
22
24
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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Kurukshetra

Challenge Name

WarmUp Challenge NIT_KKR

Notifications
View All Notifications