Chef and Tetris
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef loves Tetris. He keeps on playing Tetris all the time. Today Chef's mother wanted to him play something else and brought an array for her son. That is why Chef now decided to play Tetris with arrays. Here are the rules of the game:
- Chef has an array A consisting of N positive integers. This is a base array.
- Chef has an array B consisting of N positive integers. He placed this array directly above the array A. Imagine that array B is falling on array A, such that number Bi is directly above the number Ai initially.
- If element Bi falls on Ai, Ai gets increased by Bi.
- Each element Bi can be dropped by Chef on either Ai-1, Ai or Ai+1.
- Chef can't drop element out of array (for example he can't drop B0 on A-1).
- Chef wants all the elements of array A to become equal, and looking for the biggest possible value he can get.
Please help Chef in enjoying the game!!
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of elements in both arrays.
- The second line contains N space-separated integers B1, B2, ..., BN denoting the elements of the falling array.
- The third line contains N space-separated integers A1, A2, ..., AN denoting the elements of the base array.
- For each test case, output a single line containing a biggest integer Chef can get for all elements of array A or -1 if it is impossible.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 10^4
- 1 ≤ Ai ≤ 106
- 1 ≤ Bi ≤ 106
- Subtask N ≤ 15. Points: 30
- Subtask N ≤ 104. Points: 70
Input: 3 1 10 20 4 15 7 10 10 6 14 21 1 3 1 100 3 1 2 3 Output: 30 21 -1
Example case 1.
The only option in first example is to make 10 fall on 20. As we have only one element condition of equality is satisfied.
Example case 2.
Here Chef makes 15 fall on 6, 7 fall on 14, an then both elements with value 10 should fall on 1. Then all elements will become 21.
Example case 3.
There is no way for Chef to make all elements of a base array equal.
|Tags||berezin, july16, simple, simple-math|
|Time Limit:||2 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.