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: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

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

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


n=I()
a=LI()

dp=[[-inf]*3for i in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]
N=(n)//2

for i in range(n):
    dp[i][2]=max([dp[i-2-j][2-j]+a[i] for j in range(3) if i-2-j>=0]+[dp[i][2]])
    dp[i][1]=max([dp[i-2-j][1-j]+a[i] for j in range(2) if i-2-j>=0 and (i)//2<=N]+[dp[i][1]])
    dp[i][0]=max([dp[i-2-j][j]+a[i] for j in range(1) if i-2-j>=0 and (i+1)//2<=N]+[dp[i][0]])

ans=max(dp[n-1][:]+dp[n-2][:2]+dp[n-3][:1])
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    A1 = A[0::2]
    A2 = A[1::2]
    AA1 = list(accumulate([0] + A1))
    AA2 = list(accumulate([0] + A2[::-1]))
    ans = -(10 ** 20)
    for i in range(n // 2 + 1):
        temp = AA1[i] + AA2[n // 2 - i]
        ans = max(ans, temp)
else:
    print(A[2*n])
    # skip回数は0回か1回か2回
    dp = [[[-(10 ** 10)] * (2) for _ in range(3)] for _ in range(n + 2)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(3):
            # no skip
            ni = i + 1
            nj = j
            if ni < n + 1:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])
            # skip
            ni = i + 1
            nj = j + 1
            if nj < 3 and ni < n + 1:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])
    ans = dp[-1][2]
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    A1 = A[0::2]
    A2 = A[1::2]
    AA1 = list(accumulate([0] + A1))
    AA2 = list(accumulate([0] + A2[::-1]))
    ans = -(10 ** 20)
    for i in range(n // 2 + 1):
        temp = AA1[i] + AA2[n // 2 - i]
        print(temp)
        ans = max(ans, temp)
else:
    print(A[2*n])
    # skip回数は0回か1回か2回
    dp = [[[-(10 ** 10)] * (2) for _ in range(3)] for _ in range(n + 2)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(3):
            # no skip
            ni = i + 1
            nj = j
            if ni < n + 1:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])
            # skip
            ni = i + 1
            nj = j + 1
            if nj < 3 and ni < n + 1:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])
    ans = dp[-1][2]
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    A1 = A[0::2]
    A2 = A[1::2]
    AA1 = list(accumulate([0] + A1))
    AA2 = list(accumulate([0] + A2[::-1]))
    ans = 0
    for i in range(n // 2 + 1):
        ans = max(ans, AA1[i] + AA2[n // 2 - i])
else:
    print(A[2 * n])
    # skip回数は0回か1回か2回
    dp = [[-(10 ** 10)] * (3) for _ in range(n + 2)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(3):
            # no skip
            ni = i + 2
            nj = j
            if ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])
            # skip
            ni = i + 1
            nj = j + 1
            if nj < 3 and ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])
    ans = dp[-1][2]
print(ans)

Submission status: Runtime Error

Solution code:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define inf 1001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(15) << fixed;

  ll n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  map<tuple<ll, ll, ll>, ll> dp;
  dp[{0, 0, 0}] = 0;

  for (ll i = 1; i < n + 1; i++) {
    ll maxj = (i % 2 == 0)? i/2 : i/2 + 1;
    ll minj = ((n - 1) % 2 == 0)? n/2 - (n - i)/2 : n/2 - ((n - i)/2 + 1);
    for (ll j = minj; j < maxj + 1; j++) {
      dp[{i, j, 0}] = -inf;
      if (dp.count(make_tuple(i - 1, j, 0))) chmax(dp[{i, j, 0}], dp[{i - 1, j, 0}]);
      if (dp.count(make_tuple(i - 1, j, 1))) chmax(dp[{i, j, 0}], dp[{i - 1, j, 1}]);
      dp[{i, j, 1}] = -inf;
      if (dp.count(make_tuple(i - 1, j - 1, 0))) chmax(dp[{i, j, 1}], dp[{i - 1, j - 1, 0}] + a[i - 1]);
    }
  }
  cout << max(dp[{n, n/2, 0}], dp[{n, n/2, 1}]) << endl;
}

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
# at any partial solution, it is only possible to
# have either ceil(k/2) or ceil(k/2)-1 included values
# also, for the next solution, it matters if the current value was used or not.
# therefore, keep a partial 'max solution' for all 4 possibilities:
# ceil(k/2)-1, not included
# ceil(k/2)-1, included
# ceil(k/2), not included
# ceil(k/2), included
partial_solution = [[float('-inf') for _ in range(4)] for _ in range(len(a))]
partial_solution[0] = [0, float('-inf'), float('-inf'), a[0]]
partial_solution[1] = [0, float('-inf'), a[0], a[1]]
partial_solution[2] = [max(a[:2]), a[2], float('-inf'), a[0]+a[2]]
partial_solution[3] = [max(a[:3]), a[3], a[0]+a[2], max(a[0]+a[3], a[1]+a[3])]
for idx, value in enumerate(a[4:]):
  idx = idx+4
  if idx%2!=0:
    partial_solution[idx][0] = max(partial_solution[idx-1][0], partial_solution[idx-1][1])
    partial_solution[idx][1] = a[idx] + max(partial_solution[idx-2][0], partial_solution[idx-2][1])
    partial_solution[idx][2] = max(partial_solution[idx-1][2], partial_solution[idx-1][3])
    partial_solution[idx][3] = a[idx] + partial_solution[idx-1][0]
  else:
    partial_solution[idx][0] = max(partial_solution[idx-1][2], partial_solution[idx-1][3])
    partial_solution[idx][1] = a[idx] + partial_solution[idx-1][0]
    partial_solution[idx][2] = float('-inf')
    partial_solution[idx][3] = a[idx] + partial_solution[idx-1][2]
if n%2==0:
  ans = max(partial_solution[n-1][2], partial_solution[n-1][3])
else:
  ans = max(partial_solution[n-1][0], partial_solution[n-1][1])
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))

# Gives TLE
def naive_2D_dp(n, nums):
    # let dp[i][j]: maximum sum of j elements chosen from the first i elements where no two are adjacent.

    # dp[i][j] = max(dp[i-2][j-1] + nums[i], dp[i-1][j]); maximum between selecting the ith element and not selecting it. If we select, we have to use dp[i-2][j-1] to prevent adjacent.

    dp = [[0]*(n//2 + 1) for i in range(n+1)]

    # sum of 0 to select 0 elements
    for i in range(1, n+1):
        dp[i][0] = 0

    # to select one out of one.
    dp[1][1] = nums[0]

    for i in range(1, n+1):
        for j in range(1, i//2 + 1):
            dp[i][j] = max(nums[i-1] + (dp[i-2][j-1] if i>1 and j>0 else 0), dp[i-1][j] if i>0 else 0)

    print(dp[n][n//2])


# Source: https://icode54.blogspot.com/p/dp-1-atcoder-beginner-contest-162.html
def oneD_dp(n, nums):
    # let dp[i] be the maximum sum after picking i/2 elements. Two cases: i is odd, i is even. In both we choose the max from selecting i, and not selecting i.


    # Case 1) i is even (pick exactly i/2 elements): dp[i] = max(dp[i-2] + nums[i], odd indices sum). 
    # 1 2 3 4 5 6. If you pick 6 (i) you check the max of (i-2). If you don't pick 6, to pick i/2 elements you ave to pick the odd indices : 1, 3, 5.

    # Case 2) i is odd (i/2 is same as (i-1)/2 if we don't pick): dp[i] = max(dp[i-2] + nums[i], dp[i-1])

    # odd indices prefix sum needed for even case.
    oddpref = [0]*(n+1)
    oddpref[1] = nums[0]

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

oneD_dp(n, nums)

Submission status: Runtime Error

Solution code:
memo = {}
def f(k):
    if k==1:
        return A[-1]
    if k==2:
        return max(A[-1],A[-2])
    if k in memo:
        return memo[k]
    if k%2==0:
        memo[k] = max(A[-k]+f(k-2),sum(A[-k+1::2]))
    else:
        memo[k]=max(sum(A[-k+2::2]),A[-k]+f(k-2))
        if k>3:
            memo[k] = max(memo[k],A[-(k-1)]+f(k-3))
    return memo[k]

N = int(input())
A = list(map(int,input().split()))
print(f(N))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [[-10**18]*3 for _ in range(N)]
dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][2] = A[2]

for i in range(2, N):
    dp[i][0] = dp[i-2][0]+A[i]
    dp[i][1] = max(dp[i][1], dp[i-2][1]+A[i])
    
    if i>=3:
        dp[i][1] = max(dp[i][1], dp[i-3][0]+A[i])
    
    dp[i][2] = max(dp[i][2], dp[i-2][2]+A[i])
    
    if i>=3:
        dp[i][2] = max(dp[i][2], dp[i-3][1]+A[i])
    
    if i>=4:
        dp[i][2] = max(dp[i][2], dp[i-4][0]+A[i])

if N%2==0:
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))

Submission status: Runtime Error

Solution code:
def f(k):
    if k==1:
        return A[-1]
    return max(sum(A[1::2]),A[-k]+f(k-2))

N = int(input())
A = list(map(int,input().split()))
if N%2==0:
    a = max(sum(A[::2]),sum(A[1::2]))
else:
    a = f(N)
print(a)

Submission status: Runtime Error

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

if N%2 == 0:
    sum1 = sum(A[x*2] for x in range(N//2))
    sum2 = sum(A)-sum1
    print(max(sum1,sum2))
    exit()

DP = [0,0,0]
m = N//2*2
for i in range(0,m,2):
    DP[0] += A[i]
    DP[1] += A[i+1]
    DP[2] += A[i+2]

    DP[1] = max(DP[0],DP[1])
    DP[2] = max(DP[1],DP[2])

print(DP[3])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((3,n+1),-pow(10,15))
dp[1,1]=a[0]
for i in range(2,n+1):
    #l,r=max(1,n//2-(n-i+1)//2),(i+1)//2+1
    l,r=max(1,i//2-1),(i+1)//2+1
    if i%3==2:
        now,pre,prepre=2,1,0
    elif i%3==0:
        now,pre,prepre=0,2,1
    elif i%3==1:
        now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=n//2-(n-i+1)//2,i//2+1
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((n+1,n+1),-pow(10,15))
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    dp[i,1:]=np.maximum(dp[i-1,1:],dp[i-2,:-1]+a[i-1])
print(dp[n,n//2])

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = A[start]
    return memo[start, res]


print(c(0, N // 2))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(hoge) for hoge in input().split()]
DP = [[0]*3 for n in range(N)] #DP[n][y] = n桁目までみて、i//2 -1 + y個選んだときの最大値

DP[0][0] = A[0]


for n in range(N):#n桁目までみる
    DP[n][0] = DP[n-2][0] + A[n]
    DP[n][1] = max((DP[n-2][1],DP[n-3][0]))+A[n]
    DP[n][2] = max((DP[n-2][2],DP[n-3][1],DP[n-4][0]))+A[n]
print(max(DP[N-1]))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N+2)]
dp[0] = [0] * N
dp[1] = [0] * N
for i in range(N+2):
    dp[i][0] = 0
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(2,2+N):
    t = i - 2
    start = t//2
    end = t//2+3
    for j in range(max(1,start), end):
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[t])

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    for j in range((i//2)-1, ((i+1)//2)+2):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    for j in range(i//2-1, (i+1)//2+2):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    for j in range(1, (i+1)//2+2):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Runtime Error

Solution code:
def find(A):
    N = len(A)
    ans = [0]*N
    odd_sum = [0]*N
    even_sum = [0]*N
    for i in range(N):
        if i%2 == 0:
            if i-2>=0:
                even_sum[i] = even_sum[i-2] + A[i]
            else:
                even_sum[i] = A[i]
        else:
            if i-2>=0:
                odd_sum[i] = odd_sum[i-2] + A[i]
            else:
                odd_sum[i] = A[i]
    if N%2==0:
        return max(odd_sum[-1],even_sum[-2])
    
    def find_ans(M):
        if M==3:
            return max(A[0],A[1],A[2])
        elif M==2:
            return max(A[0],A[1])
        elif M==1:
            return 0
        
        if M%2==0:
            return max(even_sum[M-2],odd_sum[M-1])
        else:
            temp1 = A[M-1] + find_ans(M-2)
            temp2 = find_ans(M-1)
            return max(temp1,temp2)
    return find_ans(N)
input()
A = list(map(int,input().strip().split()))
print(find(A))

Submission status: Runtime Error

Solution code:
def roop(i)
	del a[i]
	return a[::2]

n=int(input())
a=str(input())
if n%2==0:#n/2が偶数の場合
	a1=list(a[::2]);a2=list(a[1::2])#a1=list([a[::2]])だと一つの要素のリストになる
	a11=[int(s) for s in a1]
	a22=[int(s) for s in a2]
	print(max(sum(a11),sum(a22)))
else:
	b=[roop(i) for i in range(n)]
	b1=[[int(i) for s in b] for i in list(s)]
	b2=[sum(b1[i]) for i in range(n)]
	print(max(b2))

Submission status: Runtime Error

Solution code:
n=int(input())
a=int(input())
if n%2==0:#n/2が偶数の場合
	a1=list([a[::2]]);a2=list([a[1::2]])
	print(max(sum(a1),sum(a2)))
else:
	print("奇数は無理なんじゃ")

Submission status: Runtime Error

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

dp = [0]*n
ep = [0]*n

dp[1] = max(a[:2])
dp[2] = max(a[:3])

ep[1] = a[0]
ep[2] = max(a[:2])

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from collections import defaultdict
 
from sys import stdin
import sys
sys.setrecursionlimit(10**9) 

N = stdin.readline().rstrip()
N=int(N)
a=list(map(int, stdin.readline().rstrip().split()))

dp = defaultdict(lambda: -10**18)
 
dp[(1,1)]=a[0]
dp[(2,1)]=max(a[0],a[1])
for i in range(N+1):
    dp[(i,0)]=0


if N>=3:
    for i in range(3, N+1):
        for j in range(max(1,math.ceil((i-3)/2)), int((i+1)/2)+1):
            dp[(i,j)]=np.nanmax([dp[(i-2,j-1)]+a[i-1], dp[(i-1,j)]])

    print(int(dp[(N,int(N/2))]))

if N==2:    
    print(int(dp([(2,1)])))

Submission status: Runtime Error

Solution code:
import numpy as np
import math

from sys import stdin
import sys
sys.setrecursionlimit(10**9) 

N = stdin.readline().rstrip()
N=int(N)
a=list(map(int, stdin.readline().rstrip().split()))

nan=np.nan
dp = np.zeros([N+1,N+1])
dp[:,:] = nan

 
dp[1][1]=a[0]
dp[2][1]=max(a[0],a[1])
for i in range(N+1):
    dp[i][0]=0


if N>=3:
    for i in range(3, N+1):
        for j in range(max(1,math.ceil((i-3)/2)), int((i+1)/2)+1):
            dp[i][j]=np.nanmax([dp[i-2][j-1]+a[i-1], dp[i-1][j]])

    print(int(dp[N][int(N/2)]))

if N==2:    
    print(int(dp[2][1]))

Submission status: Runtime Error

Solution code:
import numpy as np
import math

from sys import stdin
import sys
sys.setrecursionlimit(10**6) 

N = stdin.readline().rstrip()
N=int(N)
a=list(map(int, stdin.readline().rstrip().split()))

nan=np.nan
dp = np.zeros([N+1,N+1])
dp[:,:] = nan

 
dp[1][1]=a[0]
dp[2][1]=max(a[0],a[1])
for i in range(N+1):
    dp[i][0]=0


if N>=3:
    for i in range(3, N+1):
        for j in range(max(1,math.ceil((i-3)/2)), int((i+1)/2)+1):
            dp[i][j]=np.nanmax([dp[i-2][j-1]+a[i-1], dp[i-1][j]])

    print(int(dp[N][int(N/2)]))

if N==2:    
    print(int(dp[2][1]))

Submission status: Runtime Error

Solution code:
import numpy as np
import math

from sys import stdin

N = stdin.readline().rstrip()
N=int(N)
a=list(map(int, stdin.readline().rstrip().split()))


dp = np.zeros([N+1,N+1])
dp[:,:] = np.nan

dp[1][1]=a[0]
dp[2][1]=max(a[0],a[1])
for i in range(N+1):
    dp[i][0]=0


if N>=3:
    dp[3][0]=0
    for i in range(3, N+1):
        for j in range(max(1,math.ceil((i-3)/2)), int((i+1)/2)+1):
            dp[i][j]=np.nanmax([dp[i-2][j-1]+a[i-1], dp[i-1][j]])

    print(int(dp[N][int(N/2)]))

if N==2:
    print(int(dp[2][1]))

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=np.full((n+1,n+1),-1e+9)
dp[1,1]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(i//2-1,(i+1)//2+1):
            dp[i,j]=max(dp[i-2,j-1]+a[i-1],dp[i-1,j])
print(int(dp[n,n//2]))

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=np.zeros((n+1,(n+1)//2+1),np.int64)
dp[1,1]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(max(0,i//2-1),(i+1)//2+1):
            dp[i,j]=max(dp[i-2,j-1]+a[i-1],dp[i-1,j])
print(dp[n,n//2])

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=np.zeros((n+1,n+1),np.int64)
dp[1,1]=a[0]
dp[2,1]=max(a[:2])
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(max(0,i//2-1),(i+1)//2+1):
            dp[i,j]=max(dp[i-2,j-1]+a[i-1],dp[i-1,j])
print(dp[n,n//2])

Submission status: Runtime Error

Solution code:
import collections

def dfs(i, count, a):
	if i >= len(a):
		if count == 0:
			return 0
		else:
			return -float('inf')
	if count == 0:return 0

	if count > len(a) - i:
		return -float('inf')
	need = 2 * count -1
	
	return max(dfs(i+1, count , a) , dfs(i+2, count - 1, a) + a[i])
def f(a):
	return dfs(0, len(a)/2, a )

tt = 1
for t in range(tt): 
	n = int(raw_input())
	a = map(int,raw_input().split(' '))
	print f(a)

Submission status: Runtime Error

Solution code:
import collections

def dfs(i, count, a):
	if i >= len(a):
		if count == 0:
			return 0
		else:
			return -float('inf')
	if count == 0:return 0

	if count > len(a) - i:
		return -float('inf')
	need = 2 * count -1
	if len(a) - i < need:
		return -float('inf')
	return max(dfs(i+1, count , a) , dfs(i+2, count - 1, a) + a[i])
def f(a):
	return dfs(0, len(a)/2, a )

tt = 1
for t in range(tt): 
	n = int(raw_input())
	a = map(int,raw_input().split(' '))
	print f(a)

Submission status: Runtime Error

Solution code:
import collections

def dfs(i, count, a):
	if i == len(a):
		return 0

	if count == 0:return 0
	if len(a) - i == (count << 1):
		od,ev = 0,0
		s = 0
		while( i  < len(a)):
			if i % 2:
				od+= a[i]
			else:
				ev+= a[i]
			i+= 1
		return max(od,ev)
	return max(dfs(i+1, count , a) , dfs(i+2, count - 1, a) + a[i])
def f(a):
	return dfs(0, len(a)/2, a )
for t in range(1): 
	n = map(int,raw_input().split(' '))
	print f(map(int,raw_input().split(' ')))

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int, input().split()))
dp=[0]*n
dp[0]=0
dp[1]=math.max(a[0],a[1])
curr=a[0]
for i in range(2,n):
  if i&1==1:
    curr+=a[i-1]
    dp[i]=math.max(curr,dp[i-2]+a[i])
  else dp[i]=math.max(dp[i-2]+a[i],dp[i-1])
print(dp[n-1])

Submission status: Runtime Error

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    elif(n == 2):
        ans = max(A[0]+A[2],A[0]+A[3],A[0]+A[4],A[1]+A[3],A[1]+A[4],A[2]+A[4])
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) 
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # 2-1.A_odd(0からn_eまで) → A_even(n_e+2からnまで) 
        # まず、いきなりoddからはじめる場合で、A_oddの終点を定める
        for n_e in range(n-1):
            new_ans2 = A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max+1):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
    
    # 2-2. A_even(0からn_s-1まで) → A_odd(n_sからnまで)
    if(n >= 3):
        for n_s in range(1,n):
            new_ans2 = A_even_sum[n_s-1] + A_odd_sum[n] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
print(ans)

Submission status: Runtime Error

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    elif(n == 2):
        ans = max(A[0]+A[2],A[0]+A[3],A[0]+A[4],A[1]+A[3],A[1]+A[4],A[2]+A[4])
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) 
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # 2-1.A_odd(0からn_eまで) → A_even(n_e+2からnまで) 
        # まず、いきなりoddからはじめる場合で、A_oddの終点を定める
        for n_e in range(n-1):
            new_ans2 = A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max+1):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
    
    # 2-2. A_even(0からn_s-1まで) → A_odd(n_sからnまで)
    if(n >= 3):
        for n_s in range(1,n+1):
            new_ans2 = A_even_sum[n_s-1] + A_odd_sum[n] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
iseven=(n%2==0)

dp = [[-float("inf") for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]

for i in range(n):
    for k in range(3):
        if i+2<n:
            dp[i+2][k] = max(dp[i+2][k], dp[i][k] + a[i+2])
        if k<=1 and i+3<n:
            dp[i+3][k+1] = max(dp[i+3][k+1], dp[i][k] + a[i+3])
        if not iseven and k==0 and i+4<n:
            dp[i+4][k+2] = max(dp[i+4][k+2], dp[i][k] + a[i+4])


if iseven:
    ans=max([dp[-1][0],dp[-1][1]])
else:
    ans=max([dp[-3][0],dp[-2][1],dp[-1][2]])
print(ans)