I think you meant LDS. Also, the LDS must comprise of strictly positive elements. The starting from index 0 is lalso really important. Otherwise, it would fail in something like dividing 1 2 3 4 5 -6 into 5 parts. The prefix sum array gives 1 3 6 10 15 9. The LIS of this is 5, using the first 5 elements, but we can’t divide it into 5 parts with positive sum.
Yeah, LDS 
But won’t starting from index 0 be automatically taken care of since its a prefix sum? I think you meant to say that the first element of LIS should be positive?
Otherwise, it would fail in something like dividing 1 2 3 4 5 -6 into 5 parts. The prefix sum array gives 1 3 6 10 15 9. The LIS of this is 5, using the first 5 elements, but we can’t divide it into 5 parts with positive sum.
This example does not make sense to me because I do not know what K you assumed. I assume that you meant K=5, but then doesn;t this example highlight that LIS should end at last element instead of starting from index 1 ? I think you got mixed up in the convention.
Is this the final ranklist of ICPC ?
Yeah I mixed up your comment and the comment above. But I hope you get the idea.
One easy implementation to ensure all the conditions of the LIS are satisfied is to find LIS of only those prefix sums, who are positive and less than the last prefix sum. This way, we ensure that the last one is always included.
1 Like
We also did the same, But we used map of map and got AC in one submission.
Can someone please help me debug this solution for Question 3 which I made during contest. It gave runtime error but cannot find where is the problem.
anyone has any idea by when can we expect icpc results?
any rough guess?
6 Likes
@naman_bhalla Sir, I have seen your solution and understood your approach. But can you tell me how you really came up with the implementation?I felt it to be extremely hard. Did you do similar kind of problem elsewhere?
Thanks in advance…