Problem:


Score : 700 points

Problem Statement

You have an integer sequence of length N: a_1, a_2, ..., a_N.

You repeatedly perform the following operation until the length of the sequence becomes 1:

First, choose an element of the sequence.

If that element is at either end of the sequence, delete the element.

If that element is not at either end of the sequence, replace the element with the sum of the two elements that are adjacent to it. Then, delete those two elements.

You would like to maximize the final element that remains in the sequence.

Find the maximum possible value of the final element, and the way to achieve it.

Constraints

All input values are integers.

2 \leq N \leq 1000

|a_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

In the first line, print the maximum possible value of the final element in the sequence.

In the second line, print the number of operations that you perform.

In the (2+i)-th line, if the element chosen in the i-th operation is the x-th element from the left in the sequence at that moment, print x.

If there are multiple ways to achieve the maximum value of the final element, any of them may be printed.

Sample Input 1

5
1 4 3 7 5

Sample Output 1

11
3
1
4
2

The sequence would change as follows:

After the first operation: 4, 3, 7, 5

After the second operation: 4, 3, 7

After the third operation: 11(4+7)

Sample Input 2

4
100 100 -1 100

Sample Output 2

200
2
3
1

After the first operation: 100, 200(100+100)

After the second operation: 200

Sample Input 3

6
-1 -2 -3 1 2 3

Sample Output 3

4
3
2
1
2

After the first operation: -4, 1, 2, 3

After the second operation: 1, 2, 3

After the third operation: 4

Sample Input 4

9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

5000000000
4
2
2
2
2



Sample input:
5
1 4 3 7 5


Sample output:
11
3
1
4
2

Submission status: Wrong Answer

Solution code:
from math import inf
from sys import exit
def find_max_neigh_sum(arr):
    max_index = -1
    max_sum = -inf
    for i in range(1, len(arr) - 1):
        sum = arr[i - 1] + arr[i + 1]

        if sum > max_sum and not ((i == len(arr) - 2 and arr[i + 1] > sum) or (i == 1 and arr[0] > sum)) and arr[i] < sum:
            max_sum = sum
            max_index = i
    return max_sum, max_index



n = int(input())

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




operations = []
while len(arr) > 2:
    sum, index = find_max_neigh_sum(arr)

    if index == -1:
        operations.append(1)
        del arr[0]
        break

    operations.append(index + 1)
    arr[index] = sum

    del arr[index+1]
    del arr[index-1]



operations.append(arr.index(min(arr)) + 1)
print(max(arr))
print(len(operations))
for operation in operations: print(operation)

Submission status: Wrong Answer

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

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

eval=-10**20
L=-1
R=-1
for i in range(N):
    for j in range(i,N):
        if j==i:
            test=A[i]
            if eval<test:
                eval=test
                L,R=i,i
        elif (j-i)%2==0:
            if i%2==0:
                test=even[j]-even[i-1]*(i!=0)+A[j]*(A[j]<0)+A[i]*(A[i]<0)
                if eval<test:
                    eval=test
                    L,R=i,j
            else:
                test=odd[j]-odd[i-1]*(i!=0)+A[j]*(A[j]<0)+A[i]*(A[i]<0)
                if eval<test:
                    eval=test
                    L,R=i,j

print(eval)
print(N-1-R+L+(R-L)//2)
#print(L,R)

for i in range(N-1,R,-1):
    print(i+1)

for i in range(L):
    print(1)

for i in range(L+2,R-1,2):
    if A[i]>0:
        print(2)
    else:
        print(3)

Submission status: Wrong Answer

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

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

eval=-10**20
L=-1
R=-1
for i in range(N):
    for j in range(N):
        if (j-i)%2==0:
            if i%2==0:
                test=even[j]-even[i-1]*(i!=0)+A[j]*(A[j]<0)+A[i]*(A[i]<0)
                if eval<test:
                    eval=test
                    L,R=i,j
            else:
                test=odd[j]-odd[i-1]*(i!=0)+A[j]*(A[j]<0)+A[i]*(A[i]<0)
                if eval<test:
                    eval=test
                    L,R=i,j

print(eval)
print(N-1-R+L+(R-L)//2)
#print(L,R)

for i in range(N-1,R,-1):
    print(i+1)

for i in range(L):
    print(1)

for i in range(L+2,R-1,2):
    if A[i]>0:
        print(2)
    else:
        print(3)
print(2)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc092/tasks/arc092_c

寄与を残せる要素ってどんな集合？

→少なくとも連続する2つは絶対残せない
→残せるのは、偶数番目 or 奇数番目　のみ？

→少なくとも、偶奇が違う二つの要素を同時に残す方法は見当たらない

構築→右端から構築していくのが楽？(indexが変化しないので)
後ろから見ていって、取らないと決めたindと、取ると決めたやつ+1を選んでいけばよい

全て負の時はコーナーケース
"""

import sys
N = int(input())

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

esum = 0
osum = 0

if max(a) < 0:
    #コーナーケース

    maxind = 0
    for i in range(N):
        if a[maxind] < a[i]:
            maxind = i

    rem = N
    print (a[maxind])
    for i in range(maxind):
        print (1)
        rem -= 1
    while rem != 1:
        print (rem)
        rem -= 1
    sys.exit()

eve = 0
eflag = [False] * N
epicks = []
odd = 0
oflag = [False] * N
opicks = []
for i in range(N):

    if i % 2==0 and a[i] >= 0:
        eflag[i] = True
        eve += a[i]
        epicks.append(i)
    if i % 2==1 and a[i] >= 0:
        oflag[i] = True
        odd += a[i]
        opicks.append(i)

if eve > odd:

    print (eve)

    for i in range(N-1,-1,-1):

        if i < epicks[0]:
            print (1)
        elif i % 2 == 0 and eflag[i] == False:
            print (i+1)
        elif i % 2 == 1 and eflag[i-1] == True:
            print (i+1)

else:

    print (odd)

    for i in range(N-1,-1,-1):

        if i < opicks[0]:
            print (1)
        elif i % 2 == 1 and oflag[i] == False:
            print (i+1)
        elif i % 2 == 0 and oflag[i-1] == True:
            print (i+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

if max(A) <= 0:
    ma = - 10 ** 9
    for i, a in enumerate(A):
        if a > ma:
            ma = a
            mai = i
    print(ma)
    print(N - 1)
    for i in range(mai+1, N)[::-1]:
        print(i+1)
    for i in range(mai):
        print(1)
else:
    E = sum([a for a in A[::2] if a > 0])
    O = sum([a for a in A[1::2] if a > 0])
    ANS = []
    if O > E:
        ANS.append(1)
        A = A[1:]
    if len(A) % 2 == 0:
        ANS.append(len(A))
        A.pop()
    
    while len(A) > 1:
        if A[0] < 0:
            ANS.append(1)
            ANS.append(1)
            A = A[2:]
        elif A[-1] < 0:
            ANS.append(len(A))
            A.pop()
            ANS.append(len(A))
            A.pop()
        elif A[-3] < 0:
            ANS.append(len(A) - 2)
            A[-3] = A.pop()
            A.pop()
        else:
            ANS.append(len(A) - 1)
            A[-3] += A[-1]
            A.pop()
            A.pop()
    
    print(A[0])
    print(len(ANS))
    for a in ANS:
        print(a)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n = int(input())
a = list(map(int,input().split()))
x = a[::2]
y = a[1::2]
lx = len(x)
ly = len(y)
sumx = sum([max(x[i],0) for i in range(lx)])
sumy = sum([max(y[i],0) for i in range(ly)])
ansls = []
if sumx >= sumy:
  ans = sumx
  flg = 0
else:
  ans = sumy
  flg = 1
if flg:
  x = y
  lx = ly
  ansls.append(1)
  n -= 1
ls = [0]
fp = -1
fptmp = 0
for i in range(lx):
  if x[i] >= 0:
    ls.append(1)
    if fp == -1:
      fp = fptmp
  else:
    ls.append(-1)
    fptmp += 1
pnt = (n+1)//2*2-1
if pnt < n:
  ansls.append(n)
flgb = 0
if fp < 0:
  ansls.extend([1]*pnt)
else:
  while pnt > 0:
    px = (pnt+1)//2
    if not flgb and ls[px] < 0:
      ansls.append(pnt)
      ansls.append(pnt-1)
      ls.pop()
      pnt -= 2
    elif px <= fp:
      ansls.append(1)
      ansls.append(1)
      pnt -= 2
    elif ls[px] > 0:
      flgb = 1
      if px-1 <= fp:
        pnt -= 2
      elif ls[px-1] < 0:
        ansls.append(pnt-2)
        ls.pop()
        ls.pop()
        ls.append(1)
        pnt -= 2
      else:
        ansls.append(pnt-1)
        ls.pop()
        pnt -= 2
print(ans)
print(len(ansls))
print(*ansls,sep="\n")

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n = int(input())
a = list(map(int,input().split()))
x = a[::2]
y = a[1::2]
ax = list(accumulate(x))
ay = list(accumulate(y))
axmn = 0
aymn = 0
ans = 0
ansrng = [-1,-1]
for i in range((n+1)//2):
  if i == n//2:
    axmn = min(axmn,ax[i])
    if ax[i]-axmn > ans:
      ansrng[1] = 2*i+1
      ans = ax[i]-axmn
  else:
    axmn = min(axmn,ax[i])
    aymn = min(aymn,ay[i])
    if ax[i]-axmn > ans:
      ansrng[1] = 2*i+1
      ans = ax[i]-axmn
    if ay[i]-aymn > ans:
      ansrng[1] = 2*i+2
      ans = ay[i]-aymn
if ansrng[1]%2 == 0:
  if min(ay) >= 0:
    pass
  else:
    ansrng[0] = ay.index(min(ay))*2+4
else:
  if min(ax) >= 0:
    pass
  else:
    ansrng[0] = ax.index(min(ax))*2+3
if ansrng[1] == -1:
  x = a.index(max(a))+1
  print(max(a),n-1,sep="\n")
  for i in range(x-1):
    print(1)
  for i in range(n-x+1,1,-1):
    print(i)
  exit()
if ansrng[0] == -1:
  ansrng[0] = 2-ansrng[1]%2
print(ans)
print(n-(ansrng[1]-ansrng[0])//2-1)
for i in range((ansrng[1]-ansrng[0])//2):
  print(ansrng[0]+1)
for i in range(ansrng[0]-1):
  print(1)
for i in range(n-ansrng[1]+1,1,-1):
  print(i)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
data=[[],[]]
flag=[[],[]]
for i in range(N):
    data[i%2].append(A[i])
    flag[0].append(i%2)
    flag[1].append((i+1)%2)

num0=0

for i in range(len(data[0])):
    u=data[0][i]
    if u>0:
        num0+=u
    else:
        flag[0][2*i]=1

if num0==0:
    num0=max(data[0])
    flag[0]=[1 for i in range(N)]
    for i in range(len(data[0])):
        u=data[0][i]
        if u==num0:
            flag[0][2*i]=0
            break
            
num1=0

for i in range(len(data[1])):
    u=data[1][i]
    if u>0:
        num1+=u
    else:
        flag[1][2*i+1]=1
        
if num1==0:
    num1=max(data[1])
    flag[1]=[1 for i in range(N)]
    for i in range(len(data[1])):
        u=data[1][i]
        if u==num1:
            flag[1][2*i+1]=0
            break

if num0>num1:
    print(num0)
    H=flag[0]
else:
    print(num1)
    H=flag[1]
H=[0]+H
kkk=N

ans=[]

while True:
    if H[kkk]==1:
        ans.append(kkk)
        kkk-=1
    else:
        break

while kkk>0:
    if H[kkk]==0:
        kkk-=1
    else:
        cnt=0
        while H[kkk]==1:
            kkk-=1
            cnt+=1
        for j in range((cnt+1)//2,0,-1):
            ans.append(kkk+j)

print(len(ans))
for u in ans:
    print(u)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    even = sum([max(A[i], 0) for i in range(0, N, 2)])
    odd = sum([max(A[i], 0) for i in range(1, N, 2)])

    ans = []
    i = 0
    if odd > even:
        if N % 2 == 1:
            ans.append(N)
            N -= 1
        ans.append(1)
        i = 1
    else:
        if N % 2 == 0:
            ans.append(N)
            N -= 1
    flg = 1
    while True:
        if flg:
            if A[i] > 0:
                flg = 0
            else:
                ans.append(1)
                i += 1
                if i == N:
                    break
                ans.append(1)
                i += 1
                if i == N:
                    break
        else:
            if A[i+2] > 0:
                ans.append(2)
                i += 2
            else:
                ans.append(3)
                i += 2
            if i+2 >= N:
                break
    if ans[-1] == 3:
        ans.append(2)
    print(max(odd, even))
    print(len(ans))
    for x in ans:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    even = sum([max(A[i], 0) for i in range(0, N, 2)])
    odd = sum([max(A[i], 0) for i in range(1, N, 2)])

    ans = []
    i = 0
    if odd > even:
        if N % 2 == 1:
            ans.append(N)
            N -= 1
        ans.append(1)
        i = 1
    else:
        if N % 2 == 0:
            ans.append(N)
            N -= 1
    flg = 1
    while True:
        if flg:
            if A[i] > 0:
                flg = 0
            else:
                ans.append(1)
                i += 1
                if i >= N:
                    break
                ans.append(1)
                i += 1
        else:
            if A[i+2] > 0:
                ans.append(2)
                i += 2
            else:
                ans.append(3)
                i += 2
        if i+2 >= N:
            break
    if ans[-1] == 3:
        ans.append(2)
    print(max(odd, even))
    print(len(ans))
    for x in ans:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    even = sum([max(A[i], 0) for i in range(0, N, 2)])
    odd = sum([max(A[i], 0) for i in range(1, N, 2)])

    ans = []
    i = 0
    if odd > even:
        if N % 2 == 1:
            ans.append(N)
            N -= 1
        ans.append(1)
        i = 1
    else:
        if N % 2 == 0:
            ans.append(N)
            N -= 1
    flg = 1
    while True:
        if flg:
            if A[i] > 0:
                flg = 0
            else:
                ans.append(1)
                i += 1
                if i >= N:
                    break
                ans.append(1)
                i += 1
        else:
            if A[i+2] > 0:
                ans.append(2)
                i += 2
            else:
                ans.append(3)
                i += 2
        if i+2 >= N:
            break
    print(max(odd, even))
    print(len(ans))
    for x in ans:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    even = sum([max(A[i], 0) for i in range(0, N, 2)])
    odd = sum([max(A[i], 0) for i in range(1, N, 2)])

    ans = []
    i = 0
    if odd > even:
        if N % 2 == 1:
            ans.append(N)
        ans.append(1)
        i = 1
    else:
        if N % 2 == 0:
            ans.append(N)
    flg = 1
    while True:
        if flg:
            if A[i] > 0:
                flg = 0
            else:
                ans.append(1)
                ans.append(1)
                i += 2
        else:
            if A[i+2] > 0:
                ans.append(2)
                i += 2
            else:
                ans.append(3)
                i += 2
        if i >= N-2:
            break
    print(max(odd, even))
    print(len(ans))
    for x in ans:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if tot > best:
            while len(c) > 1 and not is_chosen[0]:
                del c[0], is_chosen[0]
            while len(c) > 1 and not is_chosen[-1]:
                del c[-1], is_chosen[-1]
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(1, 2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res, is_right_chosen = sum([c[i] for i in chosen]), [], False
        for i in reversed(range(n)):
            if i not in chosen:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in range(p, n, 2) if c[i] > 0])

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if i not in chosen:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i]
                elif ((i - 1) in chosen) == ((i + 1) in chosen):
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e9), []
    for p in range(2):
        c = a.copy()
        indexes = list(range(p, n, 2))

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks), None)

        if pick is None:
            continue

        chosen = set([pick] if maks <= 0 else [i for i in range(p, n, 2) if c[i] > 0])
        tot, res = sum([c[i] for i in chosen]), []

        for i in reversed(range(n)):
            if i not in chosen:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i]
                else:
                    if ((i - 1) in chosen) == ((i + 1) in chosen):
                        res += [i]
                        c[i - 1] += c[i + 1]
                        del c[i + 1], c[i]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e9), []
    for p in range(2):
        c = a.copy()
        indexes = list(range(p, n, 2))

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks), None)

        if not pick:
            continue

        chosen = set([pick] if pick <= 0 else [i for i in range(p, n, 2) if c[i] > 0])

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if i not in chosen:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i]
                else:
                    if ((i - 1) in chosen) == ((i + 1) in chosen):
                        res += [i]
                        c[i - 1] += c[i + 1]
                        del c[i + 1], c[i]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    s0 = 0
    s = 0
    i0 = []
    ii = []
    for i, a in enumerate(aa):
        if a < 0: continue
        if i % 2:
            s += a
            ii += [i]
        else:
            s0 += a
            i0 += [i]
    # 正の数がなかった場合
    if not ii + i0:
        s = max(aa)
        print(s)
        print(n - 1)
        flag = True
        for i in range(n - 1, -1, -1):
            if flag and aa[i] == s:
                flag = False
                continue
            print(i + 1)
        exit()
    if s0 > s:
        s = s0
        ii = i0
    # print(s, ii)
    # 右削除
    ans = list(range(n - 1, ii[-1], -1))
    # 中心部連結
    for j in range(len(ii) - 2, -1, -1):
        l, r = ii[j], ii[j + 1]
        ans += list(range((l + r) // 2, l, -1))
    # 左削除
    ans += [0] * ii[0]
    # print(ans)
    print(s)
    print(len(ans))
    for a in ans:
        print(a + 1)

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    s0 = 0
    s = 0
    i0 = []
    ii = []
    for i, a in enumerate(aa):
        if a < 0: continue
        if i % 2:
            s += a
            ii += [i]
        else:
            s0 += a
            i0 += [i]
    # 正の数がなかった場合
    if not ii + i0:
        s = max(aa)
        print(s)
        print(n - 1)
        flag = True
        for i in range(n - 1, -1, -1):
            if flag and aa[i] == s:
                flag = False
                continue
            print(i + 1)
        exit()
    if s0 > s:
        s = s0
        ii = i0
    # print(s, ii)
    # 右削除
    ans = list(range(n - 1, ii[-1], -1))
    # 中心部連結
    for j in range(len(ii) - 2, -1, -1):
        l, r = ii[j], ii[j + 1]
        ans += list(range((l + r) // 2, l, -1))
    # 左削除
    ans += list(range(ii[0] - 1, -1, -1))
    # print(ans)
    print(s)
    print(len(ans))
    for a in ans:
        print(a + 1)

main()

Submission status: Wrong Answer

Solution code:
def p(i):
    answer.append(i+ 1)
    if i == 0 or i == len(a)-1:
        a.pop(i)
        return
    a.pop(i)
    a[i - 1] += a[i]
    a.pop(i)
    # print(a)

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

odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]

answer = []


if odd_max == even_max == 0:
    max = -1000000001
    ind = 0
    for i in range(n):
        if a[i] > max:
            max = a[i]
            ind = i
    print(a[ind])
    print(n-1)
    for i in range(n - 1, ind, -1):
        print(i+1)
    for i in range(ind):
        print(1)
    quit()



# print(odd_max,even_max)
neg = []
flag = 0
if odd_max < even_max: flag = 1
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 == flag:
        neg.append(i)
# print(neg)




for i in range(len(neg)):
    p(neg[i])

k = len(a)
for i in range(k-1,-1,-1):
    if i % 2 != flag:
        p(i)

print(max(odd_max,even_max))
print(len(answer))
for i in range(len(answer)):
    print(answer[i])

Submission status: Wrong Answer

Solution code:
def p(i):
    answer.append(i+ 1)
    if i == 0 or i == len(a)-1:
        a.pop(i)
        return
    a.pop(i)
    a[i - 1] += a[i]
    a.pop(i)
    # print(a)

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

odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]

answer = []


if odd_max == even_max == 0:
    max = -1000000001
    ind = 0
    for i in range(n):
        if a[i] > max:
            max = a[i]
            ind = i
    print(a[ind])
    print(n-1)
    for i in range(n - 1, ind, -1):
        print(i+1)
    for i in range(ind):
        print(i+1)
    quit()



# print(odd_max,even_max)
neg = []
flag = 0
if odd_max < even_max: flag = 1
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 == flag:
        neg.append(i)
# print(neg)




for i in range(len(neg)):
    p(neg[i])

k = len(a)
for i in range(k-1,-1,-1):
    if i % 2 != flag:
        p(i)

print(max(odd_max,even_max))
print(len(answer))
for i in range(len(answer)):
    print(answer[i])

Submission status: Wrong Answer

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

odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]
# print(odd_max,even_max)
neg = []
flag = 0
if odd_max < even_max: flag = 1
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 == flag:
        neg.append(i)
# print(neg)

def p(index):
    answer.append(index + 1)
    if index == 0 or index == len(a)-1:
        a.pop(index)
        return
    a.pop(index)
    a[index - 1] += a[index]
    a.pop(index)
    # print(a)

answer = []
for i in range(len(neg)):
    p(neg[i])

k = len(a)
for i in range(k-1,-1,-1):
    if i % 2 != flag:
        p(i)

print(max(odd_max,even_max))
print(len(answer))
for i in range(len(answer)):
    print(answer[i])

Submission status: Wrong Answer

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

# a = [3,5,-12,-2,-2,8,9,-3,0]
# n = len(a)
# print(a)

odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]
# print(odd_max,even_max)
neg = []
flag = 1 #奇1偶0
if odd_max < even_max: flag = 0
# print(flag)
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 != flag:
        neg.append(i)
# print(neg)

def p(index):
    if index == 0 or index == len(a)-1:
        a.pop(index)
        print(a)
        return
    a.pop(index)
    a[index - 1] += a[index]
    a.pop(index)
    print(a
          )
answer = []
for i in range(len(neg)):
    index = neg[i]
    # p(index)
    answer.append(index+1)
    # print(a)

if n % 2 == 0:
    k = n - len(neg) * 2 - 1
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i+flag)
        # p(i+flag-1)
        # print(a)
else:
    k = n - len(neg) * 2 - flag
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i)
        # p(i-1)
        # print(a)

print(max(odd_max,even_max))
print(len(answer))
for i in range(len(answer)):
    print(answer[i])

Submission status: Wrong Answer

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

# a = [3,5,-12,-2,-2,8,9,-3,7,5]
# n = len(a)
# print(a)
odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]
# print(odd_max,even_max)
neg = []
flag = 1 #奇1偶0
if odd_max < even_max: flag = 0
# print(flag)
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 != flag:
        neg.append(i)
# print(neg)

# def p(index):
#     a.pop(index)
#     a[index - 1] += a[index]
#     a.pop(index)
answer = []
for i in range(len(neg)):
    index = neg[i]
    # p(index)
    answer.append(index+1)
    # print(a)

if n % 2 == 0:
    k = n - len(neg) * 2 - 1
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i+flag)
        # print(a)
else:
    k = n - len(neg) * 2 - flag
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i)
        # print(a)

if n % 2 == 1 and flag == 0:
    step = n//2+1

else:
    step = n//2

print(max(odd_max,even_max))
print(step)
for i in range(step):
    print(answer[i])

Submission status: Wrong Answer

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

# a = [3,5,-12,-2,-2,8,9,-3,7,5]
# n = len(a)
# print(a)
odd_max = 0
even_max = 0
for i in range(n):
    if a[i] > 0:
        if i % 2 == 0:
            odd_max += a[i]
        else:
            even_max +=a[i]
# print(odd_max,even_max)
out_max = max(odd_max,even_max)
neg = []
flag = 1 #奇1偶0
if odd_max < even_max: flag = 0
# print(flag)
for i in range(n-1,-1,-1):
    if a[i] < 0 and i % 2 != flag:
        neg.append(i)
# print(neg)

# def p(index):
#     a.pop(index)
#     a[index - 1] += a[index]
#     a.pop(index)
answer = []
for i in range(len(neg)):
    index = neg[i]
    # p(index)
    answer.append(index+1)
    # print(a)

if n % 2 == 0:
    k = n - len(neg) * 2 - 1
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i+flag)
        # print(a)
else:
    k = n - len(neg) * 2 - flag
    # print(k)
    for i in range(k,0,-2):
        # print(i)
        answer.append(i)
        # print(a)

if n % 2 == 1 and flag == 0:
    step = n//2+1

else:
    step = n//2
print(step)
print(out_max)
for i in range(step):
    print(answer[i])