KOPC12A  K12  Building Construction
Given N buildings of height h1, h2, h3 ... hn, the objective is to make every building has equal height. This can be done by removing bricks from a building or adding some bricks to a building. Removing a brick or adding a brick is done at certain cost which will be given along with the heights of the buildings. Find the minimal cost at which you can make the buildings look beautiful by reconstructing the buildings such that the N buildings satisfy
h1 = h2 = h3 = ... = hn = k (k can be any number).
For convenience, all buildings are considered to be vertical piles of bricks, which are of same dimensions.
Input
The first line of input contains an integer T which denotes number of test cases .This will be followed by 3 * T lines, 3 lines per test case. The first line of each test case contains an integer n and the second line contains n integers which denotes the heights of the buildings [h1, h2, h3 ... hn] and the third line contains n integers [c1, c2, c3 ... cn] which denotes the cost of adding or removing one unit of brick from the corresponding building.
T <= 15; n <= 10000; 0 <= Hi <= 10000; 0 <= Ci <= 10000;
Output
The output must contain T lines each line corresponding to a testcase.
Example
Input: 1 3 1 2 3 10 100 1000 Output: 120
hide comments
lucifer_1729:
20230109 15:38:40
@canhnam357 can you explain your 2 pointer approach 

canhnam357:
20220812 02:40:15
done with O(nlogn) ,sort , two_pointer Last edit: 20220812 02:41:13 

khssupriya:
20210117 12:49:38
My first AC in one go T_T 

prakharrrr4:
20201014 06:44:29
For proof of unimodality refer this:


tj2972001:
20200812 14:27:57
If anybody gets AC with Ternary search then please look at my solution I am getting WA. Logic seems correct and I am getting right answer with every test case I am thinking. plz help :/ [Link to ideone: <snip>. You can ask me dought regarding my logic (..if any) Last edit: 20220725 21:02:58 

jopdhiwaala:
20200701 07:57:10
Ternary search and binary search both work. 

aditya2020:
20200624 11:44:18
@soham_12345 or anyone, could you pls help me solve this. I've got no clue. I've tried binary search btw 0 and max, also I've tried the most trivial solution of taking the max height and calculating the val for all of them, and then taking minimum of all of them 

akarsh_raj:
20200522 08:21:24
someone please explain the example.


thanos_tapras:
20200306 23:03:28
Nice problem. Notes:


limon_88:
20191028 22:47:57
Must use long long int.. Last edit: 20191028 22:48:23 
Added by:  Radhakrishnan Venkataramani 
Date:  20120131 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 