In The Green Zone Codechef Solution
There are NN cans lying on the X-axis at points XiXi (1≤i≤N)(1≤i≤N). Each of the N cans is associated with two values AiAi and BiBi. Also, the segment between the points LL and RR (L≤R)(L≤R) is considered to be green zone including the points LL and RR. There are two types of operations –
1.1. Select a can ii out of the NN cans and move it one unit in either direction along the axis, i.e. if before the operation can is at XiXi then after the operation, it moves to either Xi+1Xi+1 or Xi−1Xi−1. This costs BiBi coins and it can be performed any number of times for each of the cans.
2.2. Choose any integer kk and shift the green zone to the segment between L′L′ and R′R′, where L′L′ and R′R′ are the mirror images of points RR and LL with respect to line X=kX=k respectively. This operation can be performed at most once.
After all the operations, you get number of coins equal to sum of values of AiAi of the cans which lie in the final green zone. We define the net coins as:
Number of coins you get – Number of coins spentNumber of coins you get – Number of coins spent
Find the maximum possible net coins you can earn.
- First line will contain TT, number of testcases. Then the testcases follow.
- Each of the testcases consists of four lines.
- First lines consists of three integers NN, LL and RR.
- Next line consist of NN space separated integers X1,X2,…,XNX1,X2,…,XN.
- Next line consist of NN space separated integers A1,A2,…,ANA1,A2,…,AN.
- Next line consist of NN space separated integers B1,B2,…,BNB1,B2,…,BN.
For each testcase, output in a single integer, the maximum number of net coins you can earn.
- Sum of NN over all test cases does not exceed 3⋅1053⋅105
Sample Input 1
2 1 7 10 2 6 1 3 7 10 2 8 1 6 20 1 1 3 2
Sample Output 1
Test case 11 : Lets choose the axis at X=5X=5 and Shift the green zone in the range [0,3][0,3], such that can lies in green zone. So, there is no need for operation of type 11 and total number of coins earned is A1A1, i.e. 66.
Test case 22 : Choose the axis at X=8X=8, so the new green zone lies in the region [6,9][6,9]. Move the can 11 to X=6X=6. Number of coins received is equal to A1+A2A1+A2 and number of coins spent is 4⋅B14⋅B1. So, the net coins earned is 20+6−4=2220+6−4=22. This is also the maximum possible.
Read More Post Here