I can not figure out why my implementation is giving WA, the implementation passes only the first subtask.
Here is what I did:-
- Made an array of pairs of A[i] and D[i] for all the n values.
- Sorted the above array on the basis of value of A[i]. Also initialised a variable sum to 0.
- Took integer variables, say lp(denoting left-pointer) and rp(right-pointer). The final sum will thus be given by number written on all the cards lying in the range [lp, rp] (rp and lp inclusive).
- Initialised lp to 1 and rp to total number of cards. That is assumed, initially all cards were selected. Now for each turn of Chef, I selected the last B[i] cards, that is assigned lp to rp - B[i] + 1 or lp = rp + B[i] - 1 and left rp untouched. Similarly for each turn of Chefu, I selected the first B[i] cards, that is assigned rp tp lp + B[i] - 1 or rp = lp + B[i] - 1 keeping lp untouched.
In this way finally sum can be obtained by summing up numbers written on all the cards in the range [lp, rp]. - Made a prefix sum array(say pr) of size n, indicating the sum of cards ending at the i’th index, using the value of D[i], that is:- pr[0] = D[0], pr[1] = D[0] + D[1], pr[2] = D[2] + pr[1], … so on. Found at what index j, pr[j] >= lp.
- Finally ran a while loop until lp equals to rp. Inside the loop if rp > pr[j] then collected all cards from lp to pr[j]. That is sum += (pr[j] - lp + 1) * D[j] (total cards to selected multiplied by their value), and set lp to pr[j] + 1(indicating all cards till pr[j] have been selected) and also incremented j. Else if (rp <= pr[j]) then collected all cards till rp using the formula sum += (rp - lp + 1) * D[j], set lp = rp + 1(indicating all cards have been selected), this will also break the loop.
- Finally printed the value of sum.
Here is the C++ implementation, which is passing the sample test case given in the question and all the test cases manually made by me. But when submitted only passes the first subtask.