Naruto and Boruto
All submissions for this problem are available.
Naruto and Boruto both are capable of generating powerful shadow clones. One day they decided to test the strength of each others shadow clones. Naruto created N shadow clones indexed from 1 to N and Boruto created M shadow clones indexed from 1 to M. Naruto's clones are attacking Boruto's clones. Whenever Naruto's Clone attack it costs Naruto some energy. Similarly whenever Boruto's clone gets attacked it costs Naruto some energy. Initially Boruto's clones have some energy. Whenever a clone of Boruto gets attacked it loses 1 unit of enrgy.
You are given an array X of length M (X1, X2, ...., XM) where Xi denotes the amount of energy ith clone of Boruto initially has. For each of the clones of Naruto you are given a list of clones of Boruto that it can attack. You are also given an array Y of length N (Y1 , Y2 , ..., YN) and an array Z of length M (Z1, Z2, ..., ZM). Whenever the ith Clone of Naruto attacks it costs Yi energy to Naruto and when the jth clone of Boruto is attacked it costs Naruto Zj amount of energy. Whenever a clone of Boruto gets attacked by Naruto it loses 1 unit of energy. Naruto's objective is to minimize Boruto's energy as much as possible. You need to find the minimum energy which Naruto will spend to achieve his objective.
The first line of input contains two space-separated integers N and M denoting the number of shadown clones of Naruto and Boruto respectively.
The second line contains N space separated integers, the ith integer of which denotes the array element Yi.
Each of the next M lines contain two space-separated integers, where the ith line contains the array elements Xi and Zi.
Each of the next N lines contains the data regarding which clones of Boruto any clone of Naruto can attack as follows :-
The ith contains Li denoting the number of clones of Boruto ith clone of Naruto can attack followed by Li space-separated integers denoting the indices of Boruto's clones that the ith clone of Naruto can attack.
The output should consist of a single integer denoting the minimum amount of energy which Naruto needs to spend to achieve his objective.
- 1 ≤ N ≤ 200
- 1 ≤ M ≤ 200
- 0 ≤ ∑ Li ≤ 500
- 0 ≤ Xi, Yi, Zi ≤ 105
1 5 9 2 3
2 1 2
2 1 2
3 1 2 3 Output: 75
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions