Zonal Computing Olympiad 2014, 30 Nov 2013

In IPL 2025, the amount that each player is paid varies from match to match.  The match fee depends on the quality of opposition, the venue etc.

The match fees for each match in the new season have been announced in advance.  Each team has to enforce a mandatory rotation policy so that no player ever plays three matches in a row during the season.

Nikhil is the captain and chooses the team for each match. He wants to allocate a playing schedule for himself to maximize his earnings through match fees during the season.  

-----Input format-----
Line 1: A single integer N, the number of games in the IPL season.
Line 2: N non-negative integers, where the integer in
position i represents the fee for match i.

-----Output format-----
The output consists of a single non-negative integer, the
maximum amount of money that Nikhil can earn during this IPL
season. 

-----Sample Input 1-----
5 
10 3 5 7 3 

-----Sample Output 1-----
23

(Explanation: 10+3+7+3)

-----Sample Input 2-----
8
3 2 3 2 3 5 1 3

-----Sample Output 2-----
17

(Explanation: 3+3+3+5+3)

-----Test data-----
There is only one subtask worth 100 marks.  In all inputs:

• 1 ≤ N ≤ 2×105
• The fee for each match is between 0 and 104, inclusive.

-----Live evaluation data-----
There are 12 test inputs on the server during the exam.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n=int(input())
l=list(map(int,input().split()))
temp=[]
for item in l:
    temp.append(item)
if(n<=3):
    print(sum(temp))
else:
    for i in range(3,n):
        temp[i]=l[i]+min(temp[i-1],temp[i-2],temp[i-3])
    res=sum(l)-min(temp[n-1],temp[n-2],temp[n-3])
    print(res)

n=int(input())
l=list(map(int,input().split()))
temp=[]
for i in range(0,len(l)):
    temp.append(0)
temp[0]=l[0]
temp[1]=l[1]
temp[2]=l[2]
if(n<=3):
    print(sum(temp))
else:
    for i in range(3,n):
        temp[i]=l[i]+min(temp[i-1],temp[i-2],temp[i-3])
    res=sum(l)-min(temp[n-1],temp[n-2],temp[n-3])
    print(res)

# cook your dish here
n=int(input())
arr=[int(x) for x in input().split()]
def solve(i,k):  ####k=2 or k=1 of k=0
    if i<0:
        return 0
    ans=0
    if dp[i][k]!=None:
        return dp[i][k]
    if k==2:
        ans=max(ans,solve(i-1,k))
        ans=max(ans,solve(i-1,k-1)+arr[i])
    elif k==1:
        ans=max(ans,solve(i-1,k-1)+arr[i])
        ans=max(ans,solve(i-1,2))
    else:
        ans=max(ans,solve(i-1,2))
    dp[i][k]=ans
    return ans

dp=[[None,None,None] for x in range(n)]
for i in range(n):
    solve(i,2)
print(dp[-1][-1])

# cook your dish here
n=int(input())
arr=list(map(int,input().split()))
dp=[0]*(n+1)
dp[0]=0
dp[1]=arr[0]
dp[2]=arr[0]+arr[1]
dp[3]=max(arr[2]+arr[0],arr[1]+arr[2],dp[-1])

for i in range(4,n+1):
    dp[i]=max(dp[i-1],arr[i-1]+dp[i-2],arr[i-1]+arr[i-2]+dp[i-3])
# print(dp)/
print(dp[-1])
# if N > 0:
#     sum[0] = Ps[0]
# if N > 1:
#     sum[1] = Ps[0] + Ps[1]
# if N > 2:
#     sum[2] = max(Ps[0] + Ps[2], max(sum[1], Ps[1] + Ps[2]))


# for i in range(3, N):
#     sum[i] = max(sum[i-2] + Ps[i], max(sum[i-1], sum[i-3] + Ps[i-1] + Ps[i]))


t=int(input())
arr=input().split()
sum=[]
i=0
while(i<len(arr)):
    if(i==0):
        sum.append(int(arr[0]))
    elif(i==1):
        sum.append(int(arr[0])+int(arr[1]))
    elif(i==2):
        sum.append(max(sum[i-2]+int(arr[i]),sum[i-1],int(arr[2])+int(arr[1])))        
    else:
        sum.append(max(max(sum[i-1], sum[i-2]+ int(arr[i])), int(arr[i]) +int(arr[i-1]) + sum[i-3]))
    i=i+1
print(sum[t-1])

# cook your dish here
N = int(input())
Ps= list(map(int, input().strip().split(" ")))
#print(Ps)

sum = [0 for i in range(N)]
if N > 0:
    sum[0] = Ps[0]
if N > 1:
    sum[1] = Ps[0] + Ps[1]
if N > 2:
    sum[2] = max(Ps[0] + Ps[2], max(sum[1], Ps[1] + Ps[2]))


for i in range(3, N):
    sum[i] = max(sum[i-2] + Ps[i], max(sum[i-1], sum[i-3] + Ps[i-1] + Ps[i]))
    
    
print(sum.pop())
"""
23
"""

n = int(input())
ipl = list(map(int, input().split()))

dp=list()

for i in range(1, n+1):
    dp.append(0)

if n == 1:
    print(ipl[0])
elif n == 2:
    print(ipl[0] + ipl[1])
elif n == 3:
    print(max(ipl[0]+ipl[1], max(ipl[0]+ipl[2], ipl[1]+ipl[2])))
else:
    summ = 0
    for i in range(0, n):
        summ += ipl[i]
        
    dp[0] = ipl[0]
    dp[1] = ipl[1]
    dp[2] = ipl[2]

    for i in range(3, n):
        dp[i] = ipl[i] + min(dp[i-1], min(dp[i-2], dp[i-3]))
    print(summ - min(dp[n-1], min(dp[n-2], dp[n-3])))


# cook your dish here
N = int(input())
matches = list(map(int,input().split()))
games = matches[:3]
for i in range(3,N):
    games.append(min(games[i-1],games[i-2],games[i-3]) + matches[i])
print(sum(matches) - min(games[-1],games[-2],games[-3]))



# cook your dish here

N = int(input().strip())
incomes = []
total_sum = 0
for i in input().strip().split(" "):
    incomes.append(int(i))
    total_sum += int(i)

stored_values = incomes[:3]
for i in range(3, N):
    stored_values.append(incomes[i] + min(stored_values[-1], stored_values[-2], stored_values[-3]))

print(total_sum - min(stored_values[-1], stored_values[-2], stored_values[-3]))


# cook your dish here
import sys
import bisect
input=sys.stdin.readline
n=int(input())
l=input().split()
li=[int(i) for i in l]
if(n<=2):
    print(sum(li))
    return
dp=[0 for i in range(n)]
dp[0]=li[0]
dp[1]=li[0]+li[1]
dp[2]=max(dp[1],li[2]+dp[0],li[1]+li[2])
for i in range(3,n):
    dp[i]=max(dp[i-1],li[i]+dp[i-2],li[i-1]+li[i]+dp[i-3])
print(dp[n-1])


n=int(input())
lis=list(map(int, input().split()))
dp=[0]*n
dp[0]=lis[0]
dp[1]=lis[1]
dp[2]=lis[2]
if(n<3):
    print(sum(lis))
    return
for i in range(3 ,len(lis)):
    dp[i]=min(dp[i-1],dp[i-2],dp[i-3])
    dp[i]+=lis[i]
print(sum(lis)-min(dp[n-1], dp[n-2], dp[n-3]))



# def recursive(List, taken_previous, idx, r) : 
#     if idx >= N : return 0
#     if taken_previous :
#         # I am not sure if you should go 2 steps even futher to check. Probably extra recursion
#         return List[idx] + max( recursive(List, False, idx + 2, r + List[idx]), recursive(List, False, idx + 3, r + List[idx]))
#     else :
#         return  List[idx] + max( recursive(List, True, idx + 1, r + List[idx]), recursive(List, False, idx + 2, r + List[idx]) )
    
# N = int(input())
# fees = list(map(int, input().split()))
# dp = [-1] * int(1e6)

# def recursive(nums, n) : 
#     if n < 0  : return 0
#     elif n == 0 : return nums[0]
#     elif n == 1 : return nums[0] + nums[1]
#     else : 
#         if dp[n] != -1 : return dp[n]
        
#         dp[n] = max( recursive(nums, n - 1), 
#                      recursive(nums, n - 2) + nums[n],
#                      recursive(nums, n - 3) + nums[n] + nums[n-1]
#                     )
        
#         return dp[n]
        
    
# if N <= 2 :  print(sum(fees))
# else :
#     r = recursive(fees, N - 1)
#     print(r)
    
    
dp = [-1] * int(1e6)


def solve(a, d):
	if d < 0:
		return 0
	if d == 0:
		return a[0]
	if d == 1:
		return a[0] + a[1]

	if dp[d] != -1:
		return dp[d]

	dp[d] = max(
		solve(a, d - 1),
		solve(a, d - 2) + a[d],
		solve(a, d - 3) + a[d] + a[d - 1]
	)
	return dp[d]


def main():
	from sys import stdin, stdout, setrecursionlimit
	setrecursionlimit(int(1e6))
	rl = stdin.readline

	n = int(rl())
	a = [int(x) for x in rl().split()]

	if n < 3:
		stdout.write(str(sum(a)))
		return

	stdout.write(str(solve(a, n - 1)))


main()
    

    


# cook your dish here
no = int(input())
alls = list(input().split())
dp = [0]*(no+1)
if(no==1):
	dp[1]=alls[0]
	print(dp[1])
elif(no==2):
	dp[2] = int(alls[1])+int(alls[0])
	print(dp[2])
elif(no>=3):
	dp[1]= int(alls[0])
	dp[2] = int(alls[1])+int(alls[0])
	a = int(alls[0])+int(alls[1])		
	b = int(alls[1])+int(alls[2])
	c = int(alls[0])+int(alls[2])		
	dp[3] = max(a,b,c)
	for x in range(4,(no+1)):
		d = int(dp[x-2]) + int(alls[x-1])
		e = int(dp[x-1])
		f = int(dp[x-3]+int(alls[x-2])+int(alls[x-1]))
		dp[x] = max(d,e,f)
	print(dp[no])


n = int(input())
a = list(map(int,input().split()))
dp = [[0]*3 for i in range(n+1)]

for i in range(1,n+1):
    dp[i][0] = max(dp[i-1])
    for j in range(1,3):
        dp[i][j] = max(dp[i][j],dp[i-1][j-1] + a[i-1])

print(max(dp[-1]))        


# cook your dish here
n=int(input())
array=list(map(int, input().split()))
appo2=sum(array)
for i in range(3,n):
    array[i]+=min([array[i-1],array[i-2],array[i-3]])
appo=min([array[-1],array[-2],array[-3]])
print(appo2-appo)


from sys import stdin, stdout
import math,sys,heapq
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import random
import bisect as bi
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))
#sys.setrecursionlimit(1500)
def dict(a):
    d={} 
    for x in a:
        if d.get(x,-1)!=-1:
            d[x]+=1
        else:
            d[x]=1
    return d
def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bi.bisect_left(a, x)
    if i != len(a):
        return i
    else:            
        return -1
def main():
    try:
        n=I()
        l=list(In())
        dp=[[0,0] for x in range(n)]
        if n==1:
            print(l[0])
        elif n==2:
            print(sum(l))
        else:
            dp[2][0]=l[2]+l[1]
            dp[2][1]=l[2]+l[0]
            ma=max(dp[1][0],dp[1][1])
            dp[1][1]=l[1]
            dp[1][0]=l[1]+l[0]
            for i in range(3,n):
                dp[i][0]=l[i]+dp[i-1][1]
                ma=max(dp[i-2][0],dp[i-2][1],ma)
                dp[i][1]=ma+l[i]
            ma=0
            # for i in range(n):
            #     print(dp[i][0],end=" ")
            # print()
            # for i in range(n):
            #     print(dp[i][1],end=" ")
            # print()
            for i in range(n):
                ma=max(dp[i][0],ma,dp[i][1])
            print(ma)
                
    except:
        pass
        
M = 998244353
P = 1000000007
 
def __starting_point():
    #for _ in range(I()):main()
    for _ in range(1):main()
__starting_point()

# cook your dish here
n = int(input())
l = list(map(int, input().split()))

if n <=2 :
    print(sum(l))
else:
    ml = [l[0], l[0]+l[1], max(l[0]+l[1], l[1]+l[2], l[0]+l[2])]
    for i in range(3, n):
        new = max(ml[i-1], l[i] + ml[i-2], l[i] + l[i-1] + ml[i-3])
        ml.append(new)
    print(ml[-1])

from sys import stdin,stdout
for _ in range(1):#int(stdin.readline())):
    n=int(stdin.readline())
    a=list(map(int,stdin.readline().split()))
    con0=con1=con2=0
    con1=a[0]
    for i in range(1,n):
        con0,con1,con2=max(con0,con1,con2),a[i]+con0,a[i]+con1
    print(max(con0,con1,con2))

from sys import stdin,stdout
for _ in range(1):#int(stdin.readline())):
    n=int(stdin.readline())
    a=list(map(int,stdin.readline().split()))
    con0=con1=con2=0
    con1=a[0]
    for i in range(1,n):
        con0,con1,con2=max(con0,con1,con2),a[i]+con0,a[i]+con1
    print(max(con0,con1,con2))

from sys import stdin,stdout,setrecursionlimit
setrecursionlimit(10**6)
def fn(pos,consecutive):
    if pos>=n:return 0
    if (pos,consecutive) in dp:return dp[pos,consecutive]
    take_cur=0
    if consecutive+1<3:take_cur=a[pos]+fn(pos+1,consecutive+1)
    dp[pos,consecutive]=max(take_cur,fn(pos+1,0))
    return dp[pos,consecutive]
for _ in range(1):#int(stdin.readline())):
    n=int(stdin.readline())
    a=list(map(int,stdin.readline().split()))
    dp={}
    print(fn(0,0))

# cook your dish here
import sys
read = lambda: sys.stdin.readline().strip()


n = int(read())
nums = list(map(int, read().split()))
dp = [0] * n
dp[0] = nums[0]
dp[1] = nums[1]
dp[2] = nums[2]
s = sum(nums)
for i in range(3, n):
    dp[i] = min(dp[i-1], dp[i-2], dp[i-3]) + nums[i]

print(s - min(dp[-1], dp[-2], dp[-3]))

# cook your dish here
import sys
read = lambda: sys.stdin.readline().strip()


n = int(read())
nums = list(map(int, read().split()))
dp = [0] * n
dp[0] = nums[0]
dp[1] = nums[1]
dp[2] = nums[2]
s = sum(nums)
for i in range(2, n):
    dp[i] = min(dp[i-1], dp[i-2], dp[i-3]) + nums[i]

print(s - min(dp[-1], dp[-2], dp[-3]))

# cook your dish here
N = int(input())
list1 = list(map(int,input().split()))
nextint=[0 for i in range(N)]
notnext=[ 0 for i in range(N)]
notnext[-1] = list1[-1]
nextint[-1] = list1[-1]
notnext[-2] = list1[-2]
nextint[-2] = list1[-2]+list1[-1]
for j in range(len(list1)-3,-1,-1):
    nextint[j] = max(list1[j]+notnext[j+1], nextint[j+1])
    notnext[j] = list1[j]+max(nextint[j+2],notnext[j+2]) 
#print("nextint: ",nextint,"notnext: ",notnext)
print(max(nextint[0],notnext[0]))

# cook your dish here
N = int(input())
list1 = list(map(int,input().split()))
nextint=[0 for i in range(N)]
notnext=[ 0 for i in range(N)]
notnext[-1] = list1[-1]
nextint[-1] = list1[-1]
notnext[-2] = list1[-2]
nextint[-2] = list1[-2]+list1[-1]
for j in range(len(list1)-3,-1,-1):
    nextint[j] = max(list1[j]+notnext[j+1], nextint[j+1])
    notnext[j] = list1[j]+max(nextint[j+2],notnext[j+2]) 
#print("nextint: ",nextint,"notnext: ",notnext)
print(max(nextint[0],notnext[0]))