Charlie and the Chocolate Factory
All submissions for this problem are available.
Charlie Bucket is a kind and loving boy living in poverty with his parents and four bedridden grandparents.Down the street are Willy Wonka's ‘N’ chocolate factories & ‘M’ houses.
A Godown lying adjacent to the factories holds the raw materials for the factories. It is assumed that 1g of raw material produces 1 chocolate. The transfer of raw materials to the factories is to take place for ‘Q’ days.For each day, the factories lying between the two indices L and R(inclusive), are provided with ‘K’ grams of raw materials each.(Values of L and R could differ for each day)
The houses in the city are also believed to have supply of raw materials which they can transfer it to the factories and get chocolates in return.No other house could get the chocolates made from these raw materials, except the supplying one.
There are ‘E’ eligible factories which can transfer chocolates to households. For each of the eligible factories, the indices of houses for which it is allowed to provide chocolates and the additional amount of raw materials that the houses wish to provide them are listed.
After the raw materials’ retrieval gets completed , the process of transferring chocolates from factories to the houses take place. Due to some old custom, each factory could transfer its chocolates to at most one house and each house could get the chocolates from at most one factory.
Wonka announces a contest whereby children, who find the optimal arrangement, such that the sum of the chocolates delivered to all the houses is maximum, will be given a tour of the factories and win a chance to be presented with an unknown grand prize.
Help Charlie Bucket win the contest.
The first line contains an integer ‘T’ , the number of test cases. ‘T’ test cases follow :
The first line of each test case contains two integers: N,the number of factories and M,the number of houses.
The next line contains an integer ‘Q’,the number of days for which the transfer of raw materials take place.’Q’ lines follow:
Each of the ‘Q’ lines contains three integers : L ,R and K.
L and R : Indices of the factories
K : Amount of raw material in ‘grams’.
The next line contains an integer ‘E’, the number of eligible
For each of the ‘E’ factories :
The first line contains two integers ‘F’,the index of the eligible factory and ‘H’,the number of houses for which the ‘F’th factory is allowed to transfer chocolates.’H’ lines follow:
Each of the ‘H’ lines contains two integers ‘Hi’ and ‘R’, the index of the house and the amount of raw materials(in grams) the ‘Hi’th house provides ‘F’.
For each test case,print a single line: The maximum sum of the chocolates of all houses.
1 3 1
2 3 2
|Time Limit:||0.3 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.