PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef can spend A_i hours at the gym on day i.
However, he’ll only go on alternate days. What’s the maximum amount of time he can spend at the gym?
EXPLANATION:
Chef can either attend on days 1, 3, 5, \ldots or 2, 4, 6, \ldots
Simply compute the total time for both cases and print the maximum, i.e. the answer is the maximum of
A_1 + A_3 + A_5 + \ldots
and
A_2 + A_4 + A_6 + \ldots
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()))
print(max(sum(a[::2]), sum(a[1::2])))