Moving to New Office
Practice
4.2 (21 votes)
Medium
Problem
24% Success 3000 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

Ad-optimization team is moving to their new office Safina Towers :) . But the problem is Safina towers don't have furniture, but you have wood-sheet. You are given a wood-sheet of length L . Since everyone wants to create their desk in their own style you have to give them some amount of wood. So, you are given N mark-down points (since ad-optimization team have n members) from that points you have to cut the wood sheet. But the problem is wood-cutter will cost (X * left) + (Y * right) for cutting the wood (where left and right is the size of the remaining parts of the wood after cutting). For example you want to cut a wood sheet of length 10 and X=3 and Y=4 and you want to cut at point 7 then left segment size = (7-1) =6 and right segment size = (10-7) = 3 then wood cutter will cost 3 * 6+4 * 3 = 30 .

As Amazonian you have to follow frugality leadership principal, you want to give wood cutter a minimum amount of money and want to cut wood-sheet from every marking point between 1 to L (exclusive ) . please note that in all the test case first mark point=1 and last mark point = size of sheet (L). Please output minimum amount of money needed for every test case.

Input Format: T: number of test cases (1<=T<=5) For each test case:

first line contains X and Y.(X: multiplier for left segment ,Y : multiplier for right segment) 2<=X<=100 2<=Y<=100

Second line Contains N: Number of marking points (2<=N<=100)

Third line contains marking point : m(0),m(1) ..... , m(n-1) marking points on wood sheet ,where m(0)=1 and m(n-1) = L where 2<=L<=200000

Output : For each test case : Minimum amount of money you have to pay to wood cutter. Each test case answer must be printed on a new line

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
Tags:
AlgorithmsGraphsMedium
Points:20
495 votes
Tags:
ApprovedData StructuresEasyImplementation
Points:30
6 votes
Tags:
MediumAd-HocLazy Propagation in Interval/Segment TreesAdvanced Data StructuresData Structures普通
Editorial

No editorial available for this problem.