I need help with a competitive programming problem

It is considered an array of a[1], a[2], …, a[n] of nonzero natural numbers. For two indices 1 ≤ i <j <n, we note with X = a [1] + a [2] + … + a [i], Y = a [i + 1] + a [i + 2] + … + a [j] and Z = a [j + 1] + a [j + 2] + … + a [n].
Determine two indices i and j so that the difference max (X, Y, Z) - min (X, Y, Z) is minimal.
I need an O(nlogn) solution. This problem is from another website.

Could you please post the link to the question?

3 Likes

Is the array sorted?
What’s the maximum size that the array can be?
Can you share a link to the original question?

This is not in English.

  • 1 ≤ n ≤ 200 000
  • 1 ≤ a[i] ≤ 10 000
    The array is not sorted. You need to use partial sums in vector.
    The time limit is 0.2 seconds