Corrected.
Aim is simple. We have K elements. Select N-K more elements such that sum is maximized. But cannot select elements such that absolute difference is greater than X. So, we start from min+x, the maximum element which can be included, and check each number smaller tham it in reverse order, till we find N-K elements. Since n is upto 1e9 , we need to process multiple elements in a range simultaneously, as explained above.
@tarzan_1407 can you please tell why my solution is getting RUNTIME ERROR(sigsegv).
Inconvenience is regretted.
There was a confusion.
We intended the constraint on pi to apply only on first K elements, which are given in input. Remaining elements can be greater than 1e9.
Let Function f(N) be Sum of first N natural numbers is given by (N+1)*N/2. For a range [L, R] (Both L and R inclusive), sum of range is f® - f(L-1).
Consider test case
9 3 10
1 5 10
In this, first add (1+5+10) to answer. Then, add an element min+x+1 = 12 to array and sort it.
Array looks like 1 5 10 12. This means that we can include N-k = 6 elements {11}, {9,8,7,6}, {4,3,2}. Now, see that ideal strategy is to include largest numbers.
After adding 11 to sum, since we know that (5, 10) contains 4 elements while we need 5 elements, we add whole range. 6+7+8+9 = f(9) - f(5), f(n) denotes sum of first n natural numbers.
It means For a range [L, R] (Both L and R inclusive), sum of range is f(R-1) - f(L) ?
Anyone, please clear my doubt .
It means, for a range [L,R] (Both L and R EXCLUSIVE) sum of range is f(R-1) - f(L). We don’t include elements in array, since we already added them to sum in first step.
If we go for having a number smaller than minimum of the pi’s, even then, it would voilate the maximum difference constraint. But the problem statement Guarantee that a valid sequence always exist, which means that this case cannot appear in test cases.
It was intended that the constraint on maximum value to be applicable on first K items only.