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

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def check(A, operations):
    c = A[:]
    for o in operations:
        if o == 1:
            A = A[1:]
        elif o == len(A):
            A = A[:len(A) - 1]
        else:
            o -= 1
            A = A[:o - 1] + [A[o - 1] + A[o + 1]] + A[o + 2:]

    if len(A) != 1:
        print(c)
        print(operations)
    assert(len(A) == 1)
    return A[0]


def solve(N, A):

    if max(A) < 0:
        ans = max(A)
        idx = A.index(ans)
        operations = []
        for i in range(N, idx + 1, -1):
            operations.append(i)
        for i in range(1, idx + 1):
            operations.append(1)
        return ans, operations

    ans = 0
    middle = []
    start, end = None, None
    for i in range(0, N, 2):
        if A[i] >= 0:
            ans += A[i]
            if start is None:
                start = i
            end = i
        else:
            if start is not None:
                middle.append(i)

    operations = []
    num = 0
    for i in range(end + 1, N):
        operations.append(N - num)
        num += 1

    for i in middle[::-1]:
        if start < i < end:
            operations.append(i + 1)
            num += 2

    for i in range(start):
        operations.append(1)
        num += 1

    for i in range((N - num) // 2):
        operations.append(2)

    return ans, operations


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

    ans1, ope1 = solve(N, A[:])
    ans2, ope2 = solve(N - 1, A[1:])
    ope2 = [1] + ope2

    if ans1 > ans2:
        print(ans1)
        print(len(ope1))
        print(*ope1, sep="\n")
    else:
        print(ans2)
        print(len(ope2))
        print(*ope2, sep="\n")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def check(A, operations):
    c = A[:]
    for o in operations:
        if o == 1:
            A = A[1:]
        elif o == len(A):
            A = A[:len(A) - 1]
        else:
            o -= 1
            A = A[:o - 1] + [A[o - 1] + A[o + 1]] + A[o + 2:]

    if len(A) != 1:
        print(c)
        print(operations)
    assert(len(A) == 1)
    return A[0]


def solve(N, A):
    ans1 = 0
    del1 = []
    ok1 = False
    start1, end1 = None, None
    for i in range(0, N, 2):
        if A[i] >= 0:
            ans1 += A[i]
            ok1 = True
            if start1 is None:
                start1 = i
            end1 = i
        else:
            if ok1:
                del1.append(i)

    ans2 = 0
    del2 = [1]
    ok2 = False
    start2 = None
    end2 = None
    for i in range(1, N, 2):
        if A[i] >= 0:
            ans2 += A[i]
            ok2 = True
            if start2 is None:
                start2 = i
            end2 = i
        else:
            if ok2:
                del2.append(i)

    ans, dele, start, end = None, None, None, None
    if ok1 and ok2:
        if ans1 > ans2:
            ans, dele, start, end = ans1, del1, start1, end1
        else:
            ans, dele, start, end = ans2, del2, start2, end2
    elif ok1:
        ans, dele, start, end = ans1, del1, start1, end1
    elif ok2:
        ans, dele, start, end = ans2, del2, start2, end2

    if not ok1 and not ok2:
        ans = max(A)
        idx = A.index(ans)
        a = []
        for i in range(N, idx + 1, -1):
            a.append(i)
        for i in range(1, idx + 1):
            a.append(1)
        return ans, a

    else:
        a = []
        num = 0
        for i in range(end + 1, N):
            a.append(N - num)
            num += 1

        for i in dele[::-1]:
            if start < i < end:
                a.append(i + 1)
                num += 2

        for i in range(start):
            a.append(1)
            num += 1

        for i in range((N - num) // 2) :
            a.append(2)

        return ans, a


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

    ans, ope = solve(N, A[:])
    print(ans)
    print(len(ope))
    print(*ope, sep="\n")

    
if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
a = map(int, raw_input().split())
S1 = S2 = 0
for i in range(N):
    if i % 2:
        if a[i] > 0:
            S1 += a[i]
    else:
        if a[i] > 0:
            S2 += a[i]
if S1 == S2 == 0:
    print max(a)
    maxm = -INF
    for i in range(N):
        if maxm < a[i]:
            maxm = a[i]
            pos = i
    a[pos] = 1
    if pos % 2:
        S1 = 1
    else:
        S2 = 1
else:
    print max(S1, S2)
ls = []
for i in range(len(a)):
    a[i] = (a[i], (i % 2 == (S1 > S2)))
while True:
    
    flag = True
    for i in range(len(a)):
        if a[i][0] < 0 and a[i][1]:
            ls.append(i + 1)
            if i == 0:
                a = a[1:]
            elif i == len(a) - 1:
                a = a[:-1]
            else:
                S = (a[i - 1][0] + a[i + 1][0], False)
                a = a[:i - 1] + [S] + a[i + 2:]
            flag = False
            break
    if not flag:
        continue
    for i in range(len(a)):
        if not a[i][1]:
            ls.append(i + 1)
            if i == 0:
                a = a[1:]
            elif i == len(a) - 1:
                a = a[:-1]
            else:
                S = (a[i - 1][0] + a[i + 1][0], True)
                a = a[:i - 1] + [S] + a[i + 2:]
            flag = False
            break
    if flag:
        break

print len(ls)
for num in ls:
    print num

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mx = max(a)
a[a.index(mx)] = abs(mx)
evn = sum(max(0, i) for i in a[::2])
odd = sum(max(0, i) for i in a[1::2])
if mx < 0:
    print(mx)
else:
    print(max(evn, odd))
oe = int(evn < odd)
res = []
beg = 0
while beg%2!=oe or a[beg]<0:
    res.append(1)
    beg += 1
end = n-1
while end%2!=oe or a[end]<0:
    res.append(end-beg+1)
    end -= 1
while beg < end:
    if a[end-2] < 0:
        res.append(end-beg-1)
    else:
        res.append(end-beg)
    end -= 2
print(len(res))
for i in res:
    print(i)

Solution (Python):
N = int(input())
*A, = map(int, input().split())

def calc(A):
    if len(A) == 1:
        return [], A[0]
    res = []
    if len(A) % 2 == 0:
        res.append(len(A))
        A = A[:-1]
    if all(a <= 0 for a in A[::2]):
        ma = max(A[::2])
        i = 0
        while A[i] != ma:
            i += 1
            res.append(1)
        j = len(A)
        while i < j-1:
            res.append(j-i)
            j -= 1
        return res, ma

    l = 0; r = len(A)
    while A[0] < 0:
        res.append(1)
        res.append(1)
        A = A[2:]
    v = 0
    while len(A) > 2:
        if A[2] < 0:
            res.append(3)
            if len(A) > 4:
                A = A[:2] + A[4:]
            else:
                A = A[:2]
        else:
            res.append(2)
            A[2] += A[0]
            A = A[2:]
    if len(A) > 1:
        res.append(2)
    return res, A[0]
r, v = calc(A)
if len(A) > 1:
    r0, v0 = calc(A[1:])
    if v < v0:
        r = [1] + r0
        v = v0
print(v, len(r), *r, sep='\n')

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq


sys.setrecursionlimit(10000)



def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    ma = -float("inf")
    st = None
    for l in xrange(n):
        s = a[l]
        for r in xrange(l+2, n, 2):
            if a[r] > 0: s += a[r]
        if s > ma:
            ma = s
            st = l

    pro = [1] * st
    a = a[st:]
    while len(a) > 1:
        if len(a) == 2:
            pro.append(2)
            a.pop(1)
        elif len(a) == 3:
            if a[2] > 0:
                pro.append(2)
            else:
                pro.append(3)
                pro.append(2)
            a.pop(2)
            a.pop(1)
        else:
            if a[2] > 0:
                pro.append(2)
                a.pop(0)
                a.pop(0)
            else:
                pro.append(3)
                a.pop(1)
                a.pop(2)

    return "\n".join(map(str, [ma, len(pro)]+pro))


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mx = max(a)
a[a.index(mx)] = abs(mx)
evn = sum(max(0, i) for i in a[::2])
odd = sum(max(0, i) for i in a[1::2])
if mx < 0:
    print(mx)
else:
    print(max(evn, odd))
oe = int(evn < odd)
res = []
beg = 0
while beg%2!=oe or a[beg]<0:
    res.append(1)
    beg += 1
end = n-1
while end%2!=oe or a[end]<0:
    res.append(end-beg+1)
    end -= 1
while beg < end:
    if a[end-2] < 0:
        res.append(end-beg-1)
    else:
        res.append(end-beg)
    end -= 2
print(len(res))
for i in res:
    print(i)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
use = [False]*n
mx = max(a)
if mx < 0:
    use[a.index(mx)] = True
else:
    evn = sum(max(i, 0) for i in a[::2])
    odd = sum(max(i, 0) for i in a[1::2])
    mx = max(evn, odd)
    for i in range(int(evn<odd), n, 2):
        if a[i] > 0:
            use[i] = True
print(mx)
beg = 0
while not use[beg]:
    beg += 1
res = [1]*beg
end = n-1
while beg < end:
    if use[end]:
        if use[end-2]:
            a[end-2] += a[end]
            res.append(end-beg)
            end -= 2
            use[end] = True
        else:
            res.append(end-beg-1)
            a[end-2] = a[end]
            end -= 2
            use[end] = True
    else:
        res.append(end-beg+1)
        end -= 1
print(len(res))
for i in res:
    print(i)

Solution (Python):
def solve(n, aaa):
    odd_idx, even_idx = [], []
    odd_sum, even_sum = 0, 0

    for i in range(0, n, 2):
        if aaa[i] > 0:
            even_idx.append(i)
            even_sum += aaa[i]
    for i in range(1, n, 2):
        if aaa[i] > 0:
            odd_idx.append(i)
            odd_sum += aaa[i]

    if odd_sum < even_sum:
        ans = even_sum
        idx = even_idx
    else:
        ans = odd_sum
        idx = odd_idx
    if ans == 0:
        import numpy as np
        i = np.argmax(aaa)
        ans = aaa[i]
        buf = list(range(n, i + 1, -1)) + [1] * i
        return ans, buf

    j = idx[-1]
    buf = list(range(n, j + 1, -1))
    for i in idx[-2::-1]:
        buf.extend(range((i + j) // 2 + 1, i + 1, -1))
        j = i
    buf += [1] * idx[0]
    return ans, buf


n = int(input())
aaa = list(map(int, input().split()))
ans, buf = solve(n, aaa)
print(ans)
print(len(buf))
print('\n'.join(map(str, buf)))