All submissions for this problem are available.
The sudden outburst of dust particles in the universe is causing serious concerns as they are moving towards our planet. The responsibility to save the planet is bestowed upon the local chef. The chef has to his disposal a destroyer missile which has the capacity to destroy a certain number of dust particles. The universe is divided into zones and a destroyer can attack a zone atmost once.
However the destroyer works in a peculiar manner. Every time the destroyer is used to destroy certain number of dust particles it needs certain amount of time to regain its full capacity which is determined by a function 'f'. Where the capacity of the destroyer at time 'j', given that it was triggered last at time 'i' (j > i) is given by f(j-i), which essentially represents the number of dust particles that can be destroyed given this scenario.
Every zone can only be attacked at a particular time instant 'i'. If the chef were to attack zone 'i' then the total number of dust particles destroyed will be the min(dust_particles_in_zone_j, f(j-i)), where time 'i' is the last time the destroyer was used.
The local chef has reached out to you for help. Given the number of dust particles in every zone along with the function 'f', your task is to identify the maximum number of dust particles that can be destroyed by the local chef.
The first line of the input consists of an integer T, representing the total number of test cases.
Every test case consists of 3 lines. The first line contains a number N, representing the total number of zones.
The following line contains N integerss_1, s_2, ..., s_N, where s_i represents the number of dust particles in the i_th zone.
The next line also contains N integers f_1, f_2, ..., f_N, where f represents the destroyer missile and f_i represents the total capacity of destruction, the number of dust particles that can be destroyed by the destroyer being triggered after 'i' seconds of the destroyer's previous use.
For every test case output a number, i.e., the maximum number of dust particles that can be destroyed by using the destroyer optimally.
1 <= T <= 50
1 <= N <= 2000
1 <= s_i <= 1000
1 <= f_i <= 1000
Input: 2 4 10 20 4 2 1 8 1 12 1 4 10 Output: 10 4
In the first test case the optimal scenario is when the destroyer is triggered at time=2 and time=4, as then the destroyer's capacity is 10, as min(8, 20)=8 and min(2,12)=2, 8+2=10 dust particles can be destroyed. Any other sequence of triggers results in the number of dust particles destroyed less than 10.
|Time Limit:||0.185185 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, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.