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: Accepted

Solution code:
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    A = LI()
    ans = -inf

    S = [0]*(N+1)
    fr = [-1]*N
    best = -1

    for i,a in enumerate(A):
        S[i] = a
        for j in range(i):
            if ((i-j)%2==0):
                if (S[j]+a>S[i]):
                    fr[i] = j
                    S[i] = S[j] + a
            if (S[i]>ans):
                ans = S[i]
                best = i
    #print(best)
    V = []
    for i in range(best+1,N)[::-1]:
        V.append(i+1)
    i = best
    while(fr[i]>=0):
        f = fr[i]
        #print(i,f)
        while(f<i):
            V.append(1+(i+f)//2)
            i -= 2
    for _ in range(i):
        V.append(1)

    print(ans)
    print(len(V))
    for v in V:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
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(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.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 = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

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

Submission status: Accepted

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)
        
if L!=R:
    print(2)

Submission status: Accepted

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])
    print (N-1)
    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)
    ans = []

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

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

    print (len(ans))
    print ("\n".join(map(str,ans)))

else:

    print (odd)
    ans = []

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

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

    print (len(ans))
    print ("\n".join(map(str,ans)))

Submission status: Accepted

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[-2] = 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: Accepted

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 sumx == sumy == 0:
  ans = max(a)
  t = a.index(max(a))
  print(ans)
  print(n-1)
  for i in range(n,t+1,-1):
    print(i)
  for i in range(t):
    print(1)
  exit()
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
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: Accepted

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]
ans=[]
ddd=0
for i in range(N):
    if H[i]==1:
        ans.append(1)
        ddd+=1
    else:
        H=H[i:]
        break   
H=[0]+H
kkk=N-ddd
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: Accepted

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)])

    if even == odd == 0:
        a = max(A)
        print(a)
        print(N-1)
        flg = 1
        for i in range(N-1):
            if A[i] == a:
                flg = 0
            if flg:
                print(1)
            else:
                print(N-i)
        exit()

    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: Accepted

Solution code:
import numpy as np


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

    sol_tot, sol_tracker = -1e10, []
    for p in range(2):
        c = a.copy()

        idx = np.arange(p, n, 2)
        if len(idx) == 0:
            continue

        pick = max(idx, key=lambda x: c[x])
        if c[pick] <= 0:
            chosen = {pick}
        else:
            chosen = {x for x in idx if c[x] > 0}

        is_chosen, tot, tracker = [False] * n, 0, []
        for i in chosen:
            is_chosen[i] = True
            tot += c[i]

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

        if len(c) > 1 and not is_chosen[0]:
            tracker += [0]
            del c[0], is_chosen[0]

        if tot > sol_tot:
            sol_tot, sol_tracker = tot, np.array(tracker) + 1

    print(sol_tot, len(sol_tracker), *sol_tracker, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


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

    sol_tot, sol_tracker = -1e10, []
    for p in range(2):
        c = a.copy()

        idx = np.arange(p, n, 2)
        if len(idx) == 0:
            continue

        pick = max(idx, key=lambda i: c[i])
        if c[pick] <= 0:
            chosen = set([pick])
        else:
            chosen = set(filter(lambda i: c[i] > 0, idx))

        is_chosen, tot, tracker = [False] * n, 0, []
        for i in chosen:
            is_chosen[i] = True
            tot += c[i]

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

        if len(c) > 1 and not is_chosen[0]:
            tracker += [0]
            del c[0], is_chosen[0]

        if tot > sol_tot:
            sol_tot, sol_tracker = tot, np.array(tracker) + 1

    print(sol_tot, len(sol_tracker), *sol_tracker, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


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

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

        idx = list(range(p, n, 2))
        if not idx:
            continue

        pick = max(idx, key=lambda i: c[i])
        if c[pick] <= 0:
            chosen = set([pick])
        else:
            chosen = set(filter(lambda i: c[i] > 0, idx))

        is_chosen, tot, tracker = [False] * n, 0, []
        for i in chosen:
            is_chosen[i] = True
            tot += c[i]

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

        if len(c) > 1 and not is_chosen[0]:
            tracker += [0]
            del c[0], is_chosen[0]

        if tot > sol_tot:
            sol_tot, sol_tracker = tot, np.array(tracker) + 1

    print(sol_tot, len(sol_tracker), *sol_tracker, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

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(filter(lambda i: c[i] == maks, indexes))
        chosen = set([pick] if maks <= 0 else filter(lambda i: c[i] > 0, indexes))
        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 len(c) > 1 and not is_chosen[0]:
            res += [0]
            del c[0], is_chosen[0]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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 len(c) > 1 and not is_chosen[0]:
            res += [0]
            del c[0], is_chosen[0]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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]

        for end in (0, ):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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]

        for end in (-1, 0):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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)
        for i in range(n - 1, -1, -1):
            if aa[i] == s:
                break
            print(i + 1)
        for _ in range(i):
            print(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: Accepted

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)
if 1 in answer: flag = 1-flag
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: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans1 = sum([a[i] for i in range(0, n, 2) if a[i] > 0])
ans2 = sum([a[i] for i in range(1, n, 2) if a[i] > 0])
if max(ans1, ans2) == 0:
	print(max(a))
	print(n-1)
	i_max = a.index(max(a))
	print(*list(range(n, i_max+1, -1)), sep="\n")
	if i_max:
		print(*[1 for _ in range(i_max)], sep="\n")

elif ans1 >= ans2:
	print(ans1)
	op = []
	left = 0
	while a[left] <= 0:
		left += 2

	right = True
	in_seg = False
	for i in range(n-1, -1, -1):
		if right:
			if i%2 == 1 or a[i] <= 0:
				op.append(i+1)
			else:
				right = False
		elif i < left:
			op += [1] * (i+1)
			break
		else:
			if in_seg == False and i%2 == 1:
				in_seg = True
				seg_right = i
			elif i%2 == 0 and a[i] > 0:
				in_seg = False
				op += list(range((i+seg_right+3)//2, i+1, -1))

	print(len(op))
	print(*op, sep="\n")

else:
	print(ans2)
	op = []
	left = 1
	while a[left] <= 0:
		left += 2

	right = True
	in_seg = False
	for i in range(n-1, -1, -1):
		if right:
			if i%2 == 0 or a[i] <= 0:
				op.append(i+1)
			else:
				right = False
		elif i < left:
			op += [1] * (i+1)
			break
		else:
			if in_seg == False and i%2 == 0:
				in_seg = True
				seg_right = i
			elif i%2 == 1 and a[i] > 0:
				in_seg = False
				op += list(range((i+seg_right+3)//2, i+1, -1))

	print(len(op))
	print(*op, sep="\n")

Submission status: Accepted

Solution code:
N = int(input())
A_ = list(map(int, input().split()))
ma = -float("inf")
ama = -1
for i, a in enumerate(A_):
    if a>0:
        break
    if ma < a:
        ma = a
        ama = i
else:
    print(ma)
    print(N-1)
    Ans = []
    for i in range(N, ama+1, -1):
        Ans.append(i)
    for i in range(ama):
        Ans.append(1)
    print("\n".join(map(str, Ans)))
    exit()

A = A_[:]

R1 = []
an1 = 0
for i in range(0, N, 2):
    a = A[i]
    if a>=0:
        an1 += a
    else:
        R1.append(i)
idx_r1 = i
R2 = []
an2 = 0
for i in range(1, N, 2):
    a = A[i]
    if a>=0:
        an2 += a
    else:
        R2.append(i)
idx_r2 = i
ans, R, idx_r = (an1, R1, idx_r1) if an1 > an2 else (an2, R2, idx_r2)
idx_r += 1
print(ans)
Ans = []

for idx in R[::-1]:
    del A[idx]
    if 1<=idx<len(A):
        A[idx-1] += A.pop(idx)
    elif idx==0:
        idx_r -= 1
    Ans.append(idx+1)
for idx in range(idx_r, -1, -2):
    if 0<=idx<len(A):
        del A[idx]
        if 1<=idx<len(A):
            A[idx-1] += A.pop(idx)
        Ans.append(idx+1)

for idx in Ans:
    del A_[idx-1]
    if 1<idx<=len(A):
        A[idx-2] += A.pop(idx-1)
# print(Ans)
assert len(A)==1 and A[0]==ans

print(len(Ans))
print("\n".join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

# 奇数番目、または偶数番目、の好きな部分集合を足せる（ただし1元以上）
# 交互に塗り分けると交互が維持されることから分かる

N = int(input())
A = np.array(input().split(), dtype=np.int64)

def select_operation(select,N):
    result = []
    # 余分な左端
    x = select.min()
    result = [0] * x
    select -= x
    N -= x
    # 余分な右端
    y = select.max()
    result += list(range(N-1,y,-1))
    N = y + 1
    # 右から見て、要らない偶数を除外
    result += np.setdiff1d(np.arange(N)[::2], select)[::-1].tolist()
    # 0,2,4,...番目を集約
    result += [1] * (len(select) - 1)
    result = [1+x for x in result]
    return result

ev_sum = np.maximum(0,A[::2]).sum()
od_sum = np.maximum(0,A[1::2]).sum()
if ev_sum >= od_sum > 0:
    select = np.where(A[::2] >= 0)[0] * 2
elif od_sum > 0:
    select = np.where(A[1::2] >= 0)[0] * 2 + 1
else:
    n = np.argmax(A)
    select = np.array([n])
S = A[select].sum()

ope = select_operation(select,N)

# 答えの出力
print(S)
print(len(ope))
print('\n'.join(map(str,ope)))

select

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
f = 1
for i in range(n):
    if a[i]>0:
        f = 0
if f:
    ind = a.index(max(a))
    print(max(a))
    list = []
    for i in range(n,ind+1,-1):
        list.append(i)
    for _ in range(ind):
        list.append(1)
    print(len(list))
    for i in list:
        print(i)
    exit()
g1 = a[1::2]
g2 = a[::2]
ans1,ans2 = 0,0
l1,l2 = [],[]
for i in range(len(g1)):
    if g1[i]>0:
        ans1 += g1[i]
        l1.append(i*2+2)
for i in range(len(g2)):
    if g2[i]>0:
        ans2 += g2[i]
        l2.append(i*2+1)
length = n
if ans1>=ans2:
    print(ans1)
    list = []
    for i in range(n,l1[-1],-1):
        list.append(i)
    length -= n-l1[-1]
    for i in range(l1[-1],l1[0],-2):
        if not i in l1:
            list.append(i)
            length -= 2
    for i in range(l1[0]-1):
        list.append(1)
    length -= l1[0]
    for _ in range(length,0,-2):
        list.append(2)
    print(len(list))
    for i in list:
        print(i)
else:
    print(ans2)
    list = []
    for i in range(n,l2[-1],-1):
        list.append(i)
    length -= n-l2[-1]
    for i in range(l2[-1],l2[0],-2):
        if not i in l2:
            list.append(i)
            length -= 2
    for i in range(l2[0]-1):
        list.append(1)
    length -= l2[0]
    for _ in range(length,0,-2):
        list.append(2)
    print(len(list))
    for i in list:
        print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(n, aa):

    opa = []

    a_max = max(aa)

    if a_max <= 0:
        print(a_max)
        x = aa.index(a_max) + 1
        for i in range(n, x, -1):
            opa.append(i)
        for i in range(1, x):
            opa.append(1)
    else:
        sum0 = 0
        sum1 = 0
        for i in range(n):
            a = aa[i]
            if 0 < a:
                if i % 2 == 0:
                    sum0 += a
                else:
                    sum1 += a
        print(max(sum0, sum1))

        used = [False] * n
        i0 = 1 if sum0 < sum1 else 0
        for i in range(i0, n, 2):
            if 0 < aa[i]:
                used[i] = True

        k = n
        for i in range(n - 1, -1, -1):
            if not used[i]:
                opa.append(i + 1)
                k -= 1
            else:
                break
        j = 0
        for i in range(k):
            if not used[i]:
                opa.append(1)
                j += 1
            else:
                break

        c = 0
        for i in range(k - 1, j - 1, -1):
            if used[i]:
                c = 0
            else:
                c += 1
                if c == 3:
                    opa.append(i - j + 2)
                    k -= 2
                    c = 1

        for i in range((k - j) // 2):
            opa.append(2)


    print(len(opa))
    for v in opa:
        print(v)


def main():
    n = input()
    n = int(n)
    aa = list(map(int, input().split()))

    solve(n, aa)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
As=[int(i) for i in input().split()]
neg_odd,neg_even=deque([]),deque([])
S_odd,S_even=0,0
for i,A in enumerate(As):
  if i%2==0:
    if A>=0:
      S_even+=A
    else:
      neg_even.append(i)
  if i%2==1:
    if A>=0:
      S_odd+=A
    else:
      neg_odd.append(i)
ans=[]
A_size=N
if S_odd==S_even==0:
  a=max(As)
  print(a)
  i=0
  while As[i]!=a:
    ans.append(1)
    i+=1
    A_size-=1
  while A_size>1:
    ans.append(A_size)
    A_size-=1
elif S_odd<=S_even:
  print(S_even)
  if N%2==0:
    ans.append(N)
    A_size-=1
  if neg_even:
    t=0
    while A_size-1==neg_even[-1]:
      neg_even.pop()
      ans.append(A_size)
      ans.append(A_size-1)
      A_size-=2
      if not neg_even:
        break
    if neg_even:
      while t==neg_even[0]:
        neg_even.popleft()
        ans.append(1)
        ans.append(1)
        t+=2
        A_size-=2
        if not neg_even:
          break
    for a in neg_even:
      ans.append(a+1-t)
      A_size-=2
      t+=2
  while A_size>1:
    ans.append(2)
    A_size-=2
else:
  print(S_odd)
  if N%2==1:
    ans.append(N)
    A_size-=1
  ans.append(1)
  A_size-=1
  if neg_odd:
    t=1
    while A_size==neg_odd[-1]:
      neg_odd.pop()
      ans.append(A_size)
      ans.append(A_size-1)
      A_size-=2
      if not neg_odd:
        break
    if neg_odd:
      while t==neg_odd[0]:
        neg_odd.popleft()
        ans.append(1)
        ans.append(1)
        t+=2
        A_size-=2
        if not neg_odd:
          break
    for a in neg_odd:
      ans.append(a-t+1)
      A_size-=2
      t+=2
  while A_size>1:
    ans.append(2)
    A_size-=2
print(len(ans))
for a in ans:
  print(a)