CARRCOL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A forest has N locations, the i-th has A_i carrots.

Find the maximum number of carrots you can collect by starting at some clearing and repeatedly moving one step left or right; while not being allowed to enter clearings L through R, inclusive.

EXPLANATION:

Suppose we start at clearing X.
X is not allowed to be in [L, R].
This means either X \lt L or X \gt R must hold.

Suppose X \lt L.
Then, since we cannot enter clearing L, we will always end up remaining to the left of clearing L.
However, to the left of L we are able to move freely and can visit every one among 1, 2, 3, \ldots, L-1.
Thus, in this case the number of carrots collected is

A_1 + A_2 + \ldots + A_{L-1}

On the other hand, if X \gt R then similarly we must always stay to the right of R, so the carrots collected will equal

A_{R+1} + A_{R+2} + \ldots + A_{N}

These are the only two choices, so the final answer is the larger of these two quantities.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, l, r = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    
    ans = 0
    if l > 1: ans = max(ans, sum(a[1:l]))
    if r < n: ans = max(ans, sum(a[r+1:]))
    print(ans)