Problem:


Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

2 \leq N \leq 2\times 10^5

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
dp = [0] * n
if n % 2:
    ret2 = 0
    dp2 = [0] * n
    dp2[0] = A[0]
    dp2[1] = A[1]
    for i in range(n):
        if i == 0:
            ret = 0
        elif i == 1:
            ret = A[1]
        elif i >= 2:
            dp2[i] = dp2[i - 2] + A[i]
            ret = max(ret, dp[i - 2] + A[i])
        elif i >= 3:
            ret = max(ret, dp[i - 3] + A[i])
        elif i >= 4:
            ret = max(ret, dp2[i - 4] + A[i])
        dp[i] = ret
    print(max(dp[-1], dp[-2], dp[-3]))
else:
    for i in range(n):
        ret = A[i]
        if i >= 2:
            ret = max(ret, dp[i - 2] + A[i])
        elif i >= 3:
            ret = max(ret, dp[i - 3] + A[i])
        dp[i] = ret
    print(max(dp[-1], dp[-2]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

if n % 2 == 0:
    b = 0
    c = 0
    for i in range(n // 2):
        b += a[i * 2]
        c += a[i * 2 + 1]
    print(max(b, c))
    exit()

if n == 3:
    ans = min(a[0], a[1])
    print(min(ans, a[2]))
    exit()

inf = - float('inf')
dp = [[inf, inf, inf] for _ in range(n)]
dp[0][0] = a[0]
dp[1][1] = a[1]
dp[2][0] = a[0] + a[2]
dp[2][2] = a[2]
dp[3][1] = max(a[0], a[1]) + a[3]

for i in range(4, n):
    if i % 2 == 0:
        dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-3][0], dp[i-2][1]) + a[i]
    temp = max(dp[i-4][0], dp[i-3][1])
    dp[i][2] = max(temp, dp[i-2][2]) + a[i]

ans = max(dp[n-1][2], dp[n-2][1])
print(max(ans, dp[n-3][0]))

Submission status: Wrong Answer

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    N = I()
    A = LI()
    O = [0]*N
    E = [0]*N
    for i in range(N):
        O[i] += O[i-1]
        E[i] += E[i-1]
        if i%2==0:
            O[i] += A[i]
        else:
            E[i] += A[i]
    #print(O,E)
    if N%2==0:
        ans = max(O[-1],E[-1])
        print(ans)
        return
    def dfs(n,k):
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res
    ans = dfs(N-1,N//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
if n%2:
  m=0
  for i in range(n-1):
    m=max(m,sum(a[j] if j<i else a[j+1] for j in range(0,n-1,2)))
    m=max(m,s-m)
  print(m)
else:
  m=sum(a[i] for i in range(0,n,2))
  print(max(m,s-m))

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))

if a%2 == 0:
    p = 0
    q = 0
    for i in range(a):
        if i%2 == 0:
            p = p + b[i]
        elif i%2 == 1:
            q = q + b[i]
    if p > q:
        print(p)
    else:
        print(q)
elif a%2 == 1:
    p = 0
    q = 0
    pList = []
    qList = []
    ab = a//2
    for i in range(a):
        if i%2 == 0:
            p = p + b[i]
            pList.append(b[i])
        elif i%2 == 1:
            q = q + b[i]
            qList.append(b[i])
    if len(pList) > ab:
        pansList = []
        for _,i in enumerate(pList):
            pansList.append(p-i)
        if max(pansList) > q:
            print(max(pansList))
        else:
            print(q)
    elif len(qList) > ab:
        qansList = []
        for _,i in enumerate(qList):
            qansList.append(q-i)
        if max(qansList) > p:
            print(max(qansList))
        else:
            print(p)
    else:
        if p > q:
            print(p)
        else:
            print(q)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
lsum = [[0]*2 for i in range(n+1)]
rsum = [[0]*2 for i in range(n+1)]
for i,x in enumerate(a):
    lsum[i+1][(i+1)%2] = lsum[i][(i+1)%2]+x
    lsum[i+1][i%2] = lsum[i][i%2]
a.reverse()
for i,x in enumerate(a):
    rsum[i+1][(i+1)%2] = rsum[i][(i+1)%2]+x
    rsum[i+1][i%2] = rsum[i][i%2]
ans = -10**18
for i in range(0,n+1):
    j = n-i
    for k in range(4):
        x=k%2
        y=k//2
        if (i%2!=x or j%2!=y) and (i+x)//2+(j+y)//2 == n//2:
            if ans < lsum[i][x]+rsum[j][y]:
                ans = lsum[i][x]+rsum[j][y]
print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())

A = list(map(int,input().split()))

if N % 2 == 0:

    e = 0
    o = 0

    for i in range(N):

        if i % 2 == 0:
            e += A[i]
        else:
            o += A[i]

    print (max(e,o))

else:

    dp = [ [float("-inf")] *3 for i in range(N+10) ]
    dp[-2][0] = 0
    dp[-1][1] = 0
    dp[0][2] = 0

    for i in range(N):

            if i % 2 == 0:
                dp[i][0] = dp[i-2][0] + A[i]
                dp[i][2] = max(dp[i-2][2] + A[i],dp[i-3][1] + A[i])
            else:
                dp[i][1] = max( dp[i-3][0] + A[i] ,dp[i-2][1] + A[i] )


    es = 0
    me = float("inf")
    for i in range(N):
        if i % 2 == 0:
            es += A[i]
            me = min(me,A[i])

    print (max(dp[N-1][2] , dp[N-2][1] , dp[N-3][0] , es - me))

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))

INF = 10 ** 15
dp = [[-INF] * N for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[1]
dp[0][1] = As[0]
dp[1][1] = As[1]

if N % 2 == 0:
    for i in range(2, N):
        dp[0][i] = dp[0][i-2] + As[i]
        dp[1][i] = max(dp[0][i-1], dp[1][i-2] + As[i])
else:
    for i in range(2, N):
        dp[0][i] = dp[0][i-2] + As[i]
        dp[1][i] = max(dp[0][i-1], dp[1][i-2] + As[i])
        dp[2][i] = max(dp[1][i-1], dp[2][i-2] + As[i])


print(max(dp[0][N-1], dp[1][N-1], dp[2][N-1]))

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################

n = int(input())
a = list(map(int, input().split()))

imp = -999999999999999999

dp = [[-1e30,-1e30,-1e30,-1e30] for i in range(n)]
#donthave-Small, donthave-Big, have-Small, have-Big

dp[0][0] = 0
dp[0][1] = imp
dp[0][2] = imp
dp[0][3] = a[0]
dp[1][0] = 0
dp[1][1] = dp[0][3]
dp[1][2] = imp
dp[1][3] = a[1]

for ii in range(n-2):
    i = 2+ii
    must = i//2
    if(i%2==0):
        dp[i][0] = max(dp[i-1][1],dp[i-1][3])
        dp[i][1] = imp
        dp[i][2] = dp[i-1][0] + a[i]
        dp[i][3] = dp[i-1][1] + a[i]
    else:
        dp[i][0] = max(dp[i-1][0],dp[i-1][2])
        dp[i][1] = max(dp[i-1][1],dp[i-1][3])
        dp[i][2] = imp
        dp[i][3] = dp[i-1][0] + a[i]
        
print(max(dp[-1][0],dp[-1][2]))

Submission status: Wrong Answer

Solution code:
n = int(input())
an = (input()).split()
a = []
while n > 1:
    a.append(int(an[n-1]))
    n = n - 2
print(sum(set(a)))

Submission status: Wrong Answer

Solution code:

N = int(input())
aa = list(map(int, input().split()))

if N % 2 == 0:
    dp = [[[0, 0] for j in range(2)] for i in range(N)]

    for i, a in enumerate(aa):
        dp[i][0][1] = dp[i - 1][0][0] + a
        dp[i][0][0] = dp[i - 1][0][1]

        dp[i][1][0] = max(dp[i - 1][1][1], dp[i - 1][0][0])
        dp[i][1][1] = dp[i - 1][1][0] + a

    print(max(max(dp[-1][0]), max(dp[-1][1])))
else:
    dp = [[[0, 0] for j in range(3)] for i in range(N)]

    for i, a in enumerate(aa):
        dp[i][0][1] = dp[i - 1][0][0] + a
        dp[i][0][0] = dp[i - 1][0][1]

        dp[i][1][0] = max(dp[i - 1][1][1], dp[i - 1][0][0])
        dp[i][1][1] = dp[i - 1][1][0] + a

        dp[i][2][0] = max(dp[i - 1][2][1], dp[i - 1][1][0])
        dp[i][2][1] = dp[i - 1][2][0] + a

    print(max(max(dp[-1][1]), dp[-1][2][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

if n % 2 == 0:
    b = 0
    c = 0
    for i in range(n // 2):
        b += a[i * 2]
        c += a[i * 2 + 1]
    print(max(b, c))
    exit()

if n == 3:
    ans = min(a[0], a[1])
    print(min(ans, a[2]))
    exit()

dp = [[0,0,0] for _ in range(n)]
dp[0][0] = a[0]
dp[1][1] = a[1]
dp[2][0] = a[0] + a[2]
dp[2][2] = a[2]
dp[3][1] = max(a[0], a[1]) + a[3]

for i in range(4, n):
    if i % 2 == 0:
        dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-3][0], dp[i-2][1]) + a[i]
    temp = max(dp[i-4][0], dp[i-3][1])
    dp[i][2] = max(temp, dp[i-2][2]) + a[i]

ans = max(dp[n-1][2], dp[n-2][1])
print(max(ans, dp[n-3][0]))

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N % 2 == 0:
        if N == 2: print(max(A))
        else:
            DP = [[-10 ** 20, -10 ** 20] for _ in range(N)]
            DP[0][0] = A[0]
            DP[1][1] = A[1]
            for i in range(2, N):
                DP[i][0] = max(DP[i][0], DP[i-2][0] + A[i])
                DP[i][1] = max(DP[i][1], DP[i-2][1] + A[i])
                if i > 2: DP[i][1] = max(DP[i][1], DP[i-3][0] + A[i])
            print(max(DP[N-2][0], DP[N-1][1]))
    else:
        DP = [[-10**20, -10**20, -10**20] for _ in range(N)]
        DP[0][0] = A[0]
        DP[1][1] = A[1]
        DP[2][2] = A[2]
        for i in range(3, N):
            DP[i][0] = max(DP[i-2][0] + A[i], DP[i][0])
            DP[i][1] = max(DP[i-2][1] + A[i], DP[i][1])
            DP[i][2] = max(DP[i-2][2] + A[i], DP[i][2])
            if i > 2: 
                DP[i][1] = max(DP[i][1], DP[i-3][0] + A[i])
                DP[i][2] = max(DP[i][2], DP[i-3][1] + A[i])
        ans = max(DP[N-1][2], DP[N-2][1])
        ans = max(ans, DP[N-3][0])

        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def selectHalf(ar):
    new_arr = []
    count = 0
    for i in ar:
        if i < 0:
            continue
        if i % 2 == 0:
            new_arr.append(i)
            count += 1
    if count > 0:
        return sum(new_arr)
    else:
        return "0"

N = int(input())
ar = list(map(int, input().rstrip().split()))
print(selectHalf(ar))

Submission status: Wrong Answer

Solution code:
n = int(input())
an = (input()).split()
a = []
while n > 1:
    a.append(int(an[n-1]))
    n = n - 2
print(sum(a))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**18

n = int(input())
a = [int(item) for item in input().split()]


# dp[i-th][wait num][used / not used]
dp = [[[-100000] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    # use in i
    for j in range(3):
        dp[i+1][j][1] = dp[i][j][0] + a[i]
    # rest in i
    for j in range(2):
        dp[i+1][j+1][0] = dp[i][j][0]
    # not use in i
    for j in range(3):
        dp[i+1][j][0] = max(dp[i][j][1], dp[i+1][j][0])

ans = -INF
if n % 2 == 0:
    for item in dp[-1][1]:
        ans = max(item, ans)
else:
    for item in dp[-1][2]:
        ans = max(item, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if not n&1:
        s = sum(a)
        s_odd = sum(a[::2])
        print(max(s_odd,s-s_odd))
        return
    dp = [-float("inf")]*3
    dp[0] = a[0]
    dp[1] = a[1]
    dp[2] = a[2]
    for i in range(2,n-1)[::2]:
        nd = [-float("inf")]*3
        nd[0] = dp[0]+a[i]
        nd[1] = max(dp[0],dp[1])+a[i+1]
        nd[2] = max(dp)+a[i+2]
        dp = [j for j in nd]
    print(max(dp))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))

if N%2==0:
    mm1 = 0
    for i in range(0,N,2):
        mm1 += A[i]
    
    mm2 = 0
    for i in range(1,N,2):
        mm2 += A[i]
    ans = max(mm1,mm2)

    print(ans)

elif N%2==1:
    lft = []
    mm = 0
    for i in range(N):
        if i%2==1:
            lft.append(0)
        else:
            mm += A[i]
            lft.append(mm)

    rgt = []
    mm = 0
    for i in range(N-1,-1,-1):
        if i%2==1:
            rgt.append(0)
        else:
            mm += A[i]
            rgt.append(mm)
    rgt = rgt[::-1]

    

    total = lft[-1]

    ans = 0
    for i in range(N):
        if i%2==1:
            ans += A[i]

    for i in range(N):
        if i%2==0:
            mm = total-A[i]
            ans = max(mm,ans)

    print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if not n&1:
        s = sum(a)
        s_odd = sum(a[::2])
        print(max(s_odd,s-s_odd))
        return
    dp = [-float("inf")]*3
    dp[0] = a[0]
    dp[1] = a[1]
    dp[2] = a[2]
    for i in range(2,n-1)[::2]:
        nd = [-float("inf")]*3
        nd[0] = dp[0]+a[i]
        nd[1] = max(dp[0],dp[1])+a[i+1]
        nd[2] = max(dp)+a[i+2]
        dp = [j for j in nd]
    print(dp[2])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
al = list(map(int, input().split()))

acc = [0]*(n+2)
for i in range(n):
    acc[i+2] += acc[i]+al[i]

def f(acc,s):
    res = -1
    for i in range(s,n,2):
        res = max(res, acc[i]-acc[s] + acc[-1]-acc[i+1])
    return res

if n%2==0:
    print(f(acc,0))
    exit()

res = -1
x = 0
for i in range(0,n,2):
    res = max(res, x+f(acc,i+1))
    x += al[i]

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
ar = list(map(int, input().rstrip().split()))
new_arr = []
for i in ar:
    if i % 2 == 0:
        new_arr.append(i)
print(sum(new_arr))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(num) for num in input().split()]
dp = [[0,0,0] for _ in range(n//2+1)]

#dp[0] = [a[0],a[1],a[2]]

for i in range(n//2):
    dp[i+1][0] = dp[i][0] + a[i*2]
    dp[i+1][1] = max(dp[i][1],dp[i][0]) + a[i*2+1]
    if n % 2 == 1:
        dp[i+1][2] = max(dp[i][2],dp[i][1],dp[i][0]) + a[i*2+2]
print(dp)
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
dp = [[0]*3 for _ in range(n+5)]
t = n%2
for i in range(n):
    dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-2][1], dp[i-3][0]) + a[i]
    if t:
        dp[i][2] = max(dp[i-2][2], dp[i-3][1], dp[i-4][0]) + a[i]
print(max(dp[n-1]))

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()


# dp = [[-INF]*3 for _ in range(N)]
def solve2():
    """

6
1 2 3 4 5 6
>> 12
6
2 1 3 4 5 6
>> 12
    :return:
    """
    assert N % 2 == 0
    even = [0]
    odd = [0]
    for v in range(N):
        if v % 2 == 0:
            even.append(even[-1] + A[v])
        else:
            odd.append(odd[-1] + A[v])

    # print(even)
    # print(odd)
    ans = 0
    for i in range(len(even)):
        ans = max(ans, even[i] + odd[-1] - odd[i])
    print(ans)


def solve():
    # dp[N][ignored]
    dp = [[-INF] * 3 for _ in range(N // 2 + 1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0

    for v in range(N):
        for ignore_count in range(3):
            flag = False
            if ignore_count == 0:
                flag = (v < N - 1 and v % 2 == 0)
                dp_slice = v // 2
            elif ignore_count == 1:
                flag = (v % 2 == 1)
                dp_slice = v // 2
            else:  # ignore_count == 2:
                flag = (v > 1 and v % 2 == 0)
                dp_slice = v // 2 - 1
            if flag:
                dp[dp_slice + 1][ignore_count] = max(dp[dp_slice][ignore_count] + A[v], dp[dp_slice + 1][ignore_count])
                if ignore_count != 2:
                    dp[dp_slice + 1][ignore_count + 1] = max(dp[dp_slice + 1][ignore_count],
                                                             dp[dp_slice + 1][ignore_count + 1])
                # if ignore_count:
                #     dp[dp_slice + 1][ignore_count] = dp[dp_slice][ignore_count - 1]

    print(max(dp[-1]))


if N % 2 == 1:
    solve()
else:
    solve2()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**18

n = int(input())
a = [int(item) for item in input().split()]

if n % 2 == 0:
    ans = max(sum(a[0::2]), sum(a[1::2]))
    print(ans)
    exit()

# dp[i-th][wait num][used / not used]
dp = [[[-INF] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    # use in i
    for j in range(3):
        dp[i+1][j][1] = dp[i][j][0] + a[i]
    # rest in i
    for j in range(2):
        dp[i+1][j+1][0] = dp[i][j][0]
    # not use in i
    for j in range(3):
        dp[i+1][j][0] = max(dp[i][j][1], dp[i+1][j][0])

ans = -INF
for item in dp[-1][2]:
    ans = max(item, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
get = n//2
i = len(numbers)-1
su = 0
for j in range(get):
    su+=numbers[i]
    i-=2
print(su)

Submission status: Wrong Answer

Solution code:
def miniMaxSum(arr):
    sum = 0
    for i in arr:
        sum += i
    print(sum - max(arr), sum - min(arr))

N = int(input())
arr = list(map(int, input().rstrip().split()))
print(miniMaxSum(arr))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A_1 = [A[i] for i in range(len(A)) if i%2!=0] 
A_2 = [A[i] for i in range(len(A)) if i%2==0] 
 
ans = 0
if N%2==0:
  sum_A_1=sum(A_1)
  sum_A_2=sum(A_2)
else:
  sum_A_1=sum(A_1)-min(A_1)
  sum_A_2=sum(A_2)-min(A_2)
  
if sum_A_1>=sum_A_2:
  ans = sum_A_1
else:
  ans = sum_A_2
 
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n<3:
    print(max(a))
    exit()
print(max(sum(a[0::2]),sum(a[1::2]),sum(a[2::2])))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = sorted(list(map(int,input().split())))

ans = 0
for i in range(N,(N//2)-1,-2):
    ans += a[i-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
d=-100000000000000
if n%2==0:
    for i in range(n//2):
        e=0
        for k in range(0,i):
            e+=a[2*k]
        for l in range(i,n//2):
            e+=a[2*l+1]
        if e>d:
            d=e
if n%2==1:
    for i in range(n//2):
        for j in range (i,n//2):
            e=0
            for k in range(0,i):
                e+=a[2*k]
            for l in range(i,j):
                e+=a[2*l+1]
            for m in range(j,n//2):
                e+=a[2*m+2]
            if e>d:
                d=e
print(d)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(num) for num in input().split()]
dp = [[0,0,0] for _ in range(int(n/2)+1)]

#dp[0] = [a[0],a[1],a[2]]

for i in range(int(n/2)):
    dp[i+1][0] = dp[i][0] + a[i*2]
    dp[i+1][1] = max(dp[i][1],dp[i][0]) + a[i*2+1]
    if n % 2 == 1:
        dp[i+1][2] = max(dp[i][2],dp[i][1],dp[i][0]) + a[i*2+2]
#print(dp)        
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
choice = int(input())//2
A_l = list(map(int,input().split()))
A_l.sort(reverse = True)
SUM = 0
for i in range(choice):
    SUM += A_l[i*2]
    
print(SUM)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += a[i]
        else:
            ans2 += a[i]
    print(max(ans1, ans2))
    exit()

ruiseki0 = [0] * (n + 10) 
ruiseki1 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    ruiseki1[i + 1] = ruiseki1[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]
    else:
        ruiseki0[i + 1] += a[i]

ans = - 10 ** 20
for i in range(n):
    if i % 2 == 1:
        tmp0 = ruiseki0[i]
        tmp1 = max(ruiseki1[n] - ruiseki1[i + 2], ruiseki0[n] - ruiseki0[i + 2])
        ans = max(ans, tmp0 + tmp1)

    if i % 2 == 0:
        tmp0 = ruiseki1[n] - ruiseki1[i + 2]
        tmp1 = max(ruiseki0[i], ruiseki1[i])
        ans = max(ans, tmp0 + tmp1)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))

sum=0
for i in range(n//2):
	sum+=a[n-1-i*2]

print(sum)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n%2 == 0:
	s = sum([x for i, x in enumerate(a) if i%2 == 0])
	print(max(s, sum(a)-s))
	sys.exit()

dp = [[-10**20 for _ in range(3)] for _ in range(n)]
dp[0][0] = a[0]
dp[0][1] = 0
dp[1][1] = a[1]
dp[0][2] = 0
dp[1][2] = 0
dp[2][2] = a[2]

for i in range(1, n):
	if i%2 == 0:
		if i < n-1:
			dp[i][0] = dp[i-2][0] + a[i]
		else:
			dp[i][0] = dp[i-1][0]
		dp[i][1] = max(dp[i-1][1], dp[i-2][0])
		if i > 2:
			dp[i][2] = max(dp[i-2][2] + a[i], dp[i-4][0] + a[i], dp[i-3][1] + a[i])
	else:
		dp[i][0] = dp[i-1][0]
		if i > 1:
			dp[i][1] = max(dp[i-3][0] + a[i], dp[i-2][1] + a[i])
			dp[i][2] = max(dp[i-1][2], dp[i-2][1], dp[i-3][0])

print(max(dp[n-1]))

Submission status: Wrong Answer

Solution code:
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()
if N%2 == 0:
    v1 = sum(A[::2])
    v2 = sum(A[1::2])
    print(max(v1, v2))
else:
    DP = [[[0]*N for _ in range(3)] for _ in range(2)]
    DP[1][0][0] = A[0]
    DP[0][0][0] = 0
    for i in range(1, N):
        DP[1][0][i] = A[i] + DP[0][0][i-1]
        DP[1][1][i] = A[i] + DP[0][1][i-1]
        DP[1][2][i] = A[i] + DP[0][2][i-1]
        DP[0][0][i] = DP[1][0][i-1]
        DP[0][1][i] = max(DP[0][0][i-1], DP[1][1][i-1])
        DP[0][2][i] = max(DP[0][1][i-1], DP[1][2][i-1])
    print(max(DP[0][1][N-1], DP[1][1][N-1], DP[1][2][N-1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

A.sort()
N = int(N/2)
sum=0
for i in range(N):
	sum+=A[-1-2*i]
print(sum)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

if n % 2 == 0:
    ans = 0
    b = 0
    for i in range(0, n, 2):
        b += a[i]
    ans = max(ans, b)
    b = 0
    for i in range(1, n, 2):
        b += a[i]
    ans = max(ans, b)
    print(ans)
    exit()

n2 = n // 2

ans = 0
for i in range(1, n, 2):
    ans += a[i]

b = 0
for i in range(0, n, 2):
    b += a[i]

for i in range(0, n, 2):
    ans = max(ans, b - a[i])

b = [0] * n
c = [0] * n
bb = 0
cc = 0
for i in range(n):
    if i % 2 == 0:
        bb += a[i]
    else:
        cc += a[i]
    b[i] = bb
    c[i] = cc

d = [0] * n
e = [0] * n
dd = 0
ee = 0
for i in reversed(range(n)):
    if i % 2 == 0:
        dd += a[i]
    else:
        ee += a[i]
    d[i] = dd
    e[i] = ee

for i in range(0, n - 1, 2):
    ans = max(ans, c[i] + d[i + 1])
    ans = max(ans, (0 if i == 0 else b[i - 1]) + e[i])
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n%2 == 0:
	s = sum([x for i, x in enumerate(a) if i%2 == 0])
	print(max(s, sum(a)-s))
	sys.exit()

dp = [[-10**20 for _ in range(3)] for _ in range(n)]
dp[0][0] = a[0]
dp[0][1] = 0
dp[1][1] = a[1]
dp[0][2] = 0
dp[1][2] = 0
dp[2][2] = a[2]

for i in range(1, n):
	if i%2 == 0:
		if i < n-1:
			dp[i][0] = dp[i-2][0] + a[i]
		else:
			dp[i][0] = dp[i-1][0]
		dp[i][1] = dp[i-1][1]
		if i > 2:
			dp[i][2] = max(dp[i-2][2] + a[i], dp[i-4][0] + a[i], dp[i-3][1] + a[i])
	else:
		dp[i][0] = dp[i-1][0]
		if i > 1:
			dp[i][1] = max(dp[i-3][0] + a[i], dp[i-2][1] + a[i])
		dp[i][2] = dp[i-1][2]

print(max(dp[n-1]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
sums=0
for i in range(n//2):
    sums=sums+a[n-2*i-1]
print(sums)