Editorial for DMOPC '18 Contest 5 P3 - A Familiar Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For the first subtask, we can iterate over all subarrays O(N2) subarrays, and find their sum in O(N) time, keeping track of the longest one where the sum does not exceed M.

Time Complexity: O(N3)

For the second subtask, we can find the sum in O(1) time by using a prefix sum array.

Time Complexity: O(N2)

For the third subtask, we can use a 2-pointer approach. As the right pointer advances, the left pointer should point to the left-most index where the sum is less than M. Since both pointers will only move from left to right, the time complexity is O(N).

Time Complexity: O(N)


Comments

There are no comments at the moment.