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
divyansh_soni:
20181001 21:29:22
trivial upper and lower bound


soham_12345:
20180525 10:47:49
I don't understand how ternary search is applicable here! Can anyone give me proof that the function will be unimodal? Anyways better solution is possible. Hint: Prefix sums . Enjoy ;) 

roham1381:
20180222 06:49:35
badihi nis :) 

geeta:
20170705 18:02:53
Amazing Ques !! Enjoyed solving it :) 

mastik5h_1998:
20170418 21:55:52
doing without ternary search is a challenge...... 

kanna_19:
20170410 09:49:24
Can someone please tell me why can we apply ternary search here?


nurlansofiyev:
20160717 23:17:42
There is 2 algorithm. one is O(nlogn) . other algorithm run O(10000) in worst case (without binary and ternary search) Last edit: 20160717 23:59:27 

SUBHAJIT GORAI:
20160316 08:12:57
elegant O(n) solution ...no need of binary or ternary search 

Deepak :
20160303 21:21:35
ternary search.. :) 

sharif ullah:
20160218 21:22:40
re constructing !!!!!!!!!!!!!

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 