In The Green Zone ITGRZN Solution Codechef

by

In The Green Zone ITGRZN Solution Codechef

There are N cans lying on the X-axis at points Xi (1≤i≤N). Each of the N cans is associated with two values Ai and Bi. Also, the segment between the points L and R (L≤R) is considered to be green zone including the points L and R. There are two types of operations –

  1. Select a can i out of the N cans and move it one unit in either direction along the axis, i.e. if before the operation can is at Xi then after the operation, it moves to either Xi+1 or Xi−1. This costs Bi coins and it can be performed any number of times for each of the cans.
  2. Choose any integer k and shift the green zone to the segment between L′ and R′, where L′ and R′ are the mirror images of points R and L with respect to line X=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 Ai of the cans which lie in the final green zone. We define the net coins as:
Number of coins you get – Number of coins spent
Find the maximum possible net coins you can earn.

Input Format

  • First line will contain T, number of testcases. Then the testcases follow.
  • Each of the testcases consists of four lines.
  • First lines consists of three integers N, L and R.
  • Next line consist of N space separated integers X1,X2,…,XN.
  • Next line consist of N space separated integers A1,A2,…,AN.
  • Next line consist of N space separated integers B1,B2,…,BN.

Output Format
For each testcase, output in a single integer, the maximum number of net coins you can earn.

  • Constraints
  • 1≤T≤1000
  • 1≤N≤3⋅105
  • 1≤Ai,Bi≤109
  • −109≤L≤R≤109
  • −109≤Xi≤109
  • Sum of N over all test cases does not exceed 3⋅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
6
22

Explanation

  • Test case 1 : Lets choose the axis at X=5 and Shift the green zone in the range [0,3], such that can lies in green zone. So, there is no need for operation of type 1 and total number of coins earned is A1, i.e. 6.
  • Test case 2 : Choose the axis at X=8, so the new green zone lies in the region [6,9]. Move the can 1 to X=6. Number of coins received is equal to A1+A2 and number of coins spent is 4⋅B1. So, the net coins earned is 20+6−4=22. This is also the maximum possible.

SOLUTION

Program: In The Green Zone ITGRZN Solution in Python

# cook your dish here
import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(int(input())):
    n, l, r = map(int, input().split())
    x, a, b = [[*map(int, input().split())] for i in range(3)]
    d = defaultdict(int)
    gap = r - l
    for i in range(n):
        d1, d2 = divmod(a[i], b[i])
        if d2: 
            d[x[i] - d1 - 1 - gap] += d2
            d[x[i] + d1 + 1] += d2
        d[x[i] - d1 - gap] += b[i] - d2
        d[x[i] - gap] -= b[i]
        d[x[i]] -= b[i]
        d[x[i] + d1] -= d2 - b[i]
    ans, now, rate, t = 0, 0, 0, sorted(d.keys())
    for i in range(len(t) - 1):
        d0, d1, d2 = t[i+1], t[i], d[t[i]]
        rate += d2
        m = (now + rate) if (d1 - r) & 1 else 0
        now += (d0 - d1) * rate
        m = max(m, now - rate) if (d0 - r) & 1 else max(m, now)
        ans = max(ans, m)
    print(ans)

Related:

Leave a Comment

sixteen − eleven =