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)