HALFPIE - Editorial

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef sells one pie on each of N days, at price A_i on day i (all prices are even).
He must halve the price on exactly two consecutive days.
Find the maximum total amount he can earn.

EXPLANATION:

Without any discount, Chef would earn A_1 + A_2 + \ldots + A_N.

If the discount is applied on days i and i+1, Chef loses exactly half of each of those prices, i.e. \frac{A_i + A_{i+1}}{2}.

So, to maximize the earnings, we want to minimize this loss.
There are only N-1 choices of i, so just try all of them!

The answer is hence the maximum value of

\text{sum}(A) - \frac{A_i + A_{i+1}}{2}

across all 1 \le i \lt N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    s = sum(a)
    ans = 0
    for i in range(n-1):
        ans = max(ans, s - (a[i]+a[i+1])//2)
    print(ans)