Locks and Cities
All submissions for this problem are available.
There are 'n' cities in the country of ByteLand. These cities are categorized into three types of cities: C1, C2 and C3.
Chef has a master lock that he needs to open. This lock is comprised of 'k' component locks. All the k locks can be opened in a sequential manner only.
These component locks are of three types: L1, L2, and L3. Chef has a list of the types of all the k locks ( LCK , LCK ..... LCK[k].
Chef is provided with nine different costs C:
Cij : Cost of buying a key for jth type of lock from the ith city.
Chef also has a list of the types of all the n cities ( Cy,Cy....Cy[n] ) .
He can choose to start from any city 'x' and go upto city x+k-1. At each city 'x+i-1'( this will be the ith city that he has visited, i<=k) , he buys key to the lock numbered 'i' ( LCK[i] ).
Chef knows that the amount of money required to buy keys depends on his starting index 'x'.
Chef wants to spend as little money as possible. So he asks you to find the minimum possible cost for opening the master lock.
- First line contains the number of test cases T . The description of T test cases follows."
- The first line of each test case contains the numbers n and k.
- The next line contains n numbers (1 or 2 or 3) describing the type of each city. ( C1 or C2 or C3)
- The next line contains k numbers (1 or 2 or 3) describing the type of each component lock in the master lock(L1 or L2 or L3).
- The next line contains 9 numbers denoting the various values of Cij (starting from C11, C12....C32, C33).
- For each test case, output a single line containing the minimum cost of opening the master lock.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 200000
- 1 ≤ k ≤ n
- 1 ≤ Cij ≤ 1000000000
- Sum of n for all test cases ≤ 200000
Input: 1 3 2 1 2 3 1 2 2 1 1 1 1 1 1 1 1 Output: 2
Example case 1.Total cost if Chef starts at city 1 = C11+ C22 = 3.
Total cost if Chef starts at city 2 = C21+ C32 = 2.
|Time Limit:||8 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions