Problem:


Score : 400 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, arranged in a row in this order.

You can perform the following operation on this integer sequence any number of times:

Operation: Choose an integer i satisfying 1 \leq i \leq N-1. Multiply both A_i and A_{i+1} by -1.

Let B_1, B_2, ..., B_N be the integer sequence after your operations.

Find the maximum possible value of B_1 + B_2 + ... + B_N.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

-10^9 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible value of B_1 + B_2 + ... + B_N.

Sample Input 1

3
-10 5 -4

Sample Output 1

19

If we perform the operation as follows:

Choose 1 as i, which changes the sequence to 10, -5, -4.

Choose 2 as i, which changes the sequence to 10, 5, 4.

we have B_1 = 10, B_2 = 5, B_3 = 4. The sum here, B_1 + B_2 + B_3 = 10 + 5 + 4 = 19, is the maximum possible result.

Sample Input 2

5
10 -4 -8 -11 3

Sample Output 2

30

Sample Input 3

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

Sample Output 3

10000000000

The output may not fit into a 32-bit integer type.



Sample input:
3
-10 5 -4


Sample output:
19

Submission status: Runtime Error

Solution code:
import collections

N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[]
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1:
            L.append(j-i)
        elif j-i == 1:
            L.append(1)
        elif i <= X-1 and j >= Y-1:
            L.append(1+abs(X-1-i)+abs(Y-1-j))
        elif i >= X-1 and i-(X-1) > (Y-1)-i:
            L.append(j-i)            
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L.append(min(L1,L2))

c=collections.Counter(L)

for i in range(1,N):
    print(c[i])

Submission status: Runtime Error

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

hu = []
sei = []
for i in a:
	if i < 0:
		hu.append(i)
	else:
		sei.append(i)
hu.sort()
sei.sort()
if len(hu)%2 == 0:
	ans = sum(sei) + (-1)*sum(hu)
else:
	b = sei[0]
	c = hu[-1]
	if abs(b) <= abs(c):
		b *= -1
		c *= -1
	ans = sum(sei[1:]) + (-1)*sum(hu[:-1])
	ans += (b+c)
print (ans)

Submission status: Runtime Error

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

hu = []
sei = []
for i in a:
	if i < 0:
		hu.append(i)
	else:
		sei.append(i)
hu.sort()
sei.sort()
if len(hu)%2 == 0:
	ans = sum(sei) + (-1)*sum(hu)
else:
	b = sei.pop(0)
	c = hu.pop(-1)
	if abs(b) <= abs(c):
		b *= -1
		c *= -1
	ans = sum(sei) + (-1)*sum(hu)
	ans += (b+c)
print (ans)

Submission status: Runtime Error

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

hu = []
sei = []
for i in a:
	if i < 0:
		hu.append(i)
	else:
		sei.append(i)
hu.sort()
sei.sort()
if len(hu)%2 == 0:
	ans = sum(sei) + (-1)*sum(hu)
else:
	b = sei.pop(0)
	b *= -1
	c = hu.pop(-1)
	c *= -1
	ans = sum(sei) + (-1)*sum(hu)
	ans += (b+c)
print (ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = map(int,input().split())
if 0 in A:
  print(sum(A))
else:
  count=0
  min_A =100000000000000000
  for i in range(N):
    if A[i]<0:
      count=count+1
    if abs(A[i])<min_A:
      min_A = abs(A[i])
  print(sum(A)-min_A)

Submission status: Runtime Error

Solution code:
N = int(input())
A = map(int,input())
if 0 in A:
  print(sum(A))
else:
  count=0
  min_A =100000000000000000
  for i in range(N):
    if A[i]<0:
      count=count+1
    if abs(A[i])<min_A:
      min_A = abs(A[i])
  print(sum(A)-min_A)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    
    """
    もし負の数が偶数個存在すればそれらはすべて正の数にできる。
    もし負の数が奇数個存在すればそれは最終的に１個にできる。
    """

    idx = bisect_left(A, 0)
    if idx % 2 == 0:
        print(sum(A[idx:]) - sum(A[:idx]))
    else:
        cand1 = sum(A[idx:]) - sum(A[:idx]) + A[idx - 1] * 2
        cand2 = sum(A[idx:]) - sum(A[:idx]) - A[idx] * 2
        print(max(cand1, cand2))
    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

inf=float('inf')
dp=[[inf]*2 for j in range(N+1)]

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0 and m==0:
        dp[0][0]=0
        return 0
    if n==0 and m==1:
        dp[0][1]=-inf
        return -inf

    if dp[n][m] < inf:
        return dp[n][m]
    
    if m==0:
        res=chmax(rec(n-1,0)+A[n-1] ,rec(n-1,1)-A[n-1] ) 
    if m==1:
        res=chmax(rec(n-1,0)-A[n-1] ,rec(n-1,1)+A[n-1] )
     
    dp[n][m]=res

    return res

print(rec(N,0))

Submission status: Runtime Error

Solution code:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    hoge = 0
    ans = 0
    for i in range(n):
        if a[i] < 0:
            hoge += 1
    if 0 in a or hoge % 2 == 0:
        for i in range(n):
            ans += abs(a[i])
    else:
        huga = []
        for i in range(n):
            ans += abs(a[i])
            if a[i] > 0:
                huga.append(a[i])
        ans -= min(huga)*2
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np

def ABC125D(n, a):
    a = np.array(a)
    x = a[a > 0]
    y = abs(a[a < 0])
    if len(y) != 0:
        x_min = x[np.argmin(x)]
        y_min = y[np.argmin(y)]
        if y_min > x_min:
            x[np.argmin(x)] *= -1
    print(sum(x) + sum(y))

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

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))
for i in range(n):
  if A[i]<0 and A[i+1]<0:
    A[i] = -A[i]
    A[i+1] = -A[i]
  elif A[i]<0:
    if A[i]-A[i+1]<0:
      A[i] = -A[i]
      A[i+1] = -A[i]
print(sum(A))

Submission status: Runtime Error

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

if abs(A[0]) < abs(A[-1]):
    A = A[::-1]
B = list(map(abs, A))
tmp = A[0] // abs(A[0])
for i in range(1, N):
    if A[i] == 0:
        tmp = 0
        continue
    if tmp < 0:
        tmp = tmp*(A[i] // abs(A[i]))
    else:
        tmp = A[i] // abs(A[i])

if tmp < 0:
    print(sum(B) - 2 * B[-1])
else:
    print(sum(B))

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
ind=bisect.bisect_left(a,0)


if ind==0 :
  print(sum(a))
  
elif ind==n:
  if ind%2==1:
    print(-sum(a)+2*a[-1])
  else:
    print(abs(sum(a))

elif ind%2==0:

  print(-sum(a[:ind])+sum(a[ind:]))
else:
  print(-sum(a[:ind])+sum(a[ind:])-2*min(abs(a[ind]),abs(a[ind-1])))

Submission status: Runtime Error

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

l = ""
r = ""
for i in range(N):
    if l == "" and A[i] < 0: l = i
    if A[i] < 0:r = i
if (r-l+1) % 2 == 0 or (l == 0 and r == N-1):
    print(sum([abs(x) for x in A]))
else:
    a = [abs(x) for x in A]
    print(sum(a) - min(a)*2)

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
ind=bisect.bisect_left(a,0)
print(ind)

if ind==0:
  print(sum(a))

elif ind%2==0 or a[ind]==0:

  print(-sum(a[:ind])+sum(a[ind:]))
else:
  print(-sum(a[:ind])+sum(a[ind:])-2*min(abs(a[ind]),abs(a[ind-1])))

Submission status: Runtime Error

Solution code:
n  = int(input())
a = list(map(int,input().split()))
ans = 0
mn = 0
for i in range(n):
    if a[i] < 0:
        mn += 1
        a[i] = abs(a[i])
    ans += a[i]
if 0 in a or mn%2 = 0:
    print(ans)
else:
    print(ans - 2*min(a))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=[]
p=[]
s=0
c=0
for i in range(n):
    s+=abs(a[i])
    if a[i]<0:
        c+=1
        c%=2
        m.append(a[i])
    else:p.append(a[i])
if c==0:print(s)
else:
    m.sort()
    p.sort()
    if abs(m[-1])>abs(p[0]):print(s+m[-1]-p[0]-m[-1]-p[0])
    else:print(s)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Ap = sorted([i for i in A if i >= 0])
    An = sorted([i for i in A if i < 0])
    if len(An) % 2 == 0:
      return sum(Ap) - sum(An)
    return sum(Ap) - sum(An) - 2 * min(Ap[0], -An[-1])
print(main())

Submission status: Runtime Error

Solution code:
_, *a = map(int, open(0).read().split())
t = map(abs, a)
s = sum(t)
print(s if len([i for i in a if i<0])%2==0 or 0 in a else s-min(t))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
B,C=[],[]
for i in range(N):
  if A[i]>=0:
    B.append(A[i])
  else:
    C.append(-A[i])
if len(C)%2==0:
  ans=sum(B)+sum(C)
else:
  ans=sum(B)+sum(C)
  B.sort()
  C.sort()
  a=min(B[0],C[0])
  ans-=2*a
print(ans)

Submission status: Runtime Error

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    cnt_neg = 0
    abs_min = 1_000_000_005
    for a in A:
        abs_min = min(abs_min, abs(a))
        if a < 0:
            cnt_neg += 1

    ans = 0
    for a in A:
        ans += abs(a)

    if cnt_neg % 2 != 0:
        ans -= 2 * abs_min

    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n-1):
	if -a[i]-a[i+1]>=a[i]+a[i+1]:
      a[i]=-a[i]
      a[i+1]=-a[i+1]
print(sum(a))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
sum_abs, min_abs, cnt_minus = 0, 10**9, 0
for ai in a:
    if ai < 0:
        cnt_minus += 1
    abs_ai = abs(ai)
    sum_abs += abs_ai
    if abs_ai < min_abs:
        min_abs = abs_ai
if cnt_minus % 2 == 0 or a in 0:
    print(sum_abs)
else:
    print(sum_abs - 2*min_abs)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))
minus = 0
ans = 0
abs_min = float('inf')
for a in A:
  if a < 0:
    minus += 1
  ans += abs(a)
  abs_min = min(abs_min, abs(a))
if mins%2:
  ans -= abs_min*2

print(ans)

Submission status: Runtime Error

Solution code:
List = []
for _ in range(6):
  List.append(int(input()))
Count = 5
MIN = min(List[1],List[2],List[3],List[4],List[5],)
Count += List[0]//MIN if List[0]%MIN != 0 else (List[0]//MIN)-1

print(Count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
    if a[i] == 0:
        cnt -= 1000000000000
        break
    elif a[i] < 0:
        cnt += 1
a = [abs(a[i]) for i in range(n)]
if cnt < 0 or num % 2 == 0:
    print(sum(a))
else:
    print(sum(a) - 2*min(a))

Submission status: Runtime Error

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

def sel2(a,b,c):
    if a <= 0 and b <= 0 and c >= 0:
        return (-a,-b,c)
    elif a >= 0 and b <= 0 and c <= 0:
        return (a,-b,-c)
    elif a <= 0 and b >= 0 and c <= 0:
        return (-a,b,-c)
def sel1(a,b,c):
    if a <= 0 and b >= 0 and c >= 0:
        if abs(a) >= abs(b):
            return (-a,-b,c)
        else:
            return (a,b,c)
    elif a >= 0 and b <= 0 and c >= 0:
        if abs(b) == min(abs(a),abs(b),abs(c)):
            return (a,b,c)
        elif abs(a) > abs(c):
            return (a,-b,-c)
        elif abs(a) < abs(b):
            return (-a,-b,c)
    elif a >= 0 and b >= 0 and c <= 0:
        if abs(b) >= abs(c):
            return (a,-b,-c)
        else:
            return (a,b,c)
def selend(a,b):
    if a < 0 and b < 0:
        return (-a,-b)
    elif a < 0 and b > 0:
        if abs(a) > abs(b):
            return (-a,-b)
        elif abs(a) < abs(b):
            return (a,b)
    elif a > 0 and b < 0:
        if abs(a) > abs(b):
            return (a,b)
        elif abs(a) < abs(b):
            return (-a,-b)
for i in range(0,n//3+1,3):
    (p,q,r) = sel2(L[i],L[i+1],L[i+2])
    L[i] = p
    L[i+1] = q
    L[i+2] = r
#print(L)
(s,t) = selend(L[-2],L[-1])
L[-2] = s
L[-1] = t
#print(L)
print(sum(L))

Submission status: Runtime Error

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

if cnt_minus % 2 == 0:
    print(sum([abs(a[i]) for i in range(n)]))
else:
    mi = min([abs(a[i]) for i in range(n)])
    print(sum([abs(a[i]) for i in range(n)]) - 2 * mi)

Submission status: Runtime Error

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
dp = [[0, 0] for i in range(N+1)]
dp[0][1] = -(3*10**9)
for i in range(1, N+1):
    dp[i][0] = max(dp[i-1][0]+Alist[i], dp[i-1][1]-Alist[i])
    dp[i][1] = max(dp[i-1][0]-Alist[i], dp[i-1][1]+Alist[i])
print(dp[N][0])

Submission status: Runtime Error

Solution code:
import bisect
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    i = bisect.bisect_left(A, 0)
    j = bisect.bisect_right(A, 0)
    if i % 2 == 0:
        print(sum([abs(i) for i in A]))
    else:
        if i != j:
            print(sum([abs(i) for i in A]))
        elif i == N:
            print(sum([abs(i) for i in A]) - 2 * A[-1])
        else:
            if A[i] > A[i+1]:
                print(sum([abs(i) for i in A]) - 2 * A[i+1])
            else:
                print(sum([abs(i) for i in A]) - 2 * A[i])
main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
m = len(list(filter(lambda x: x < 0, a)))
s = sum(map(abs, a))
if m % 2 == 0 or a in 0:
    print(s)
else:
    print(s - 2 * min(a))

Submission status: Runtime Error

Solution code:
N, *A = map(int, open(0).read().split())
n = N//3 + (1 if N % 3 == 0 else 2)
cur_i = []

for i in range(n):
    a = A[i]
    b = A[i+1]
    c = A[i+2]

    if a < 0 and b < 0 and c < 0:
        if A[i-1] * -1 > A[i+3] * -1:
            cur_i.append(i-1)
        else:
            cur_i.append(i+3)

ans = 0
for i, a in enumerate(A):
    if i in cur_i:
        ans += a * -1
    else:
        ans += abs(a)

print(ans)

Submission status: Runtime Error

Solution code:
h = int(input())
w = int(input())
n = int(input())

if n / max(h, w) > n:
    print(n // max(h, w) + 1)
elif n / max(h, w) == 1:
    print(1)
elif n / max(h, w) < 1:
    print(1)
else:
    print(n // max(h, w))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
MINUS = 0
B = []

for i in A:
  if i < 0:
    MINUS += 1
  else:
    B.append(i)
  
if min(A) > 0:
  print(sum(A))
  exit(0)
  
ans = 0
if MINUS % 2 == 0:
  for a in A:
    ans += abs(a)
else:
  mb = min(B)
  mb_flag = True
  for a in A:
    if mb_flag and a == mb:
      mb_flag = False
      continue
    ans += abs(a)
  ans -= mb

print(ans)

Submission status: Runtime Error

Solution code:
import math
def calculate(arr1,arr2,zeroExist):
    if (len(arr1) % 2 == 0) or (zeroExist == True):
        return sum(arr2) - sum(arr1)
    else:
        return sum(arr2) - sum(arr1) - 2 * (calculateAbsSmallest(arr1,arr2))



def concatList(arr1,arr2):
    arr3 = list([])
    arr3.extend(arr1)
    arr3.extend(arr2)
    return arr3

def calculateAbsSmallest(arr1,arr2):
    arr1.sort()
    arr2.sort()
    return min(-arr1[0],arr2[0])


N = int(input())

arr1 = []
arr2 = []
zeroExist = False
for s in input().split(" "):
    if int(s) == 0:
        zeroExist = True
    if int(s) < 0:
        arr1.append(int(s))
    else:
        arr2.append(int(s))

arr1 = list(arr1)
arr2 = list(arr2)

res = calculate(arr1,arr2,zeroExist)
print(res)

Submission status: Runtime Error

Solution code:
import math
def calculate(arr1,arr2):

    if len(arr1) % 2 == 0:
        return sum(arr2) - sum(arr1)
    else:
        return sum(arr2) - sum(arr1) - 2 * (calculateAbsSmallest(arr1,arr2))


def concatList(arr1,arr2):
    arr3 = list([])
    arr3.extend(arr1)
    arr3.extend(arr2)
    return arr3

def calculateAbsSmallest(arr1,arr2):
    arr1.sort()
    arr2.sort()
    return min(-arr1[0],arr2[0])





N = int(input())

arr1 = []
arr2 = []
for s in input().split(" "):
    if int(s) < 0:
        arr1.append(int(s))
    else:
        arr2.append(int(s))

arr1 = list(arr1)
arr2 = list(arr2)

res = calculate(arr1,arr2)
print(res)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

MOD = 10**9+7

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

positive = []
negative = []
m = 0

for a in A:
    if a > 0:
        positive.append(a)
    else:
        m += 1
        negative.append(-a)

ans = sum(positive)+sum(negative)

if m%2==1:
    ans -= 2*(min(min(positive), min(negative)))

print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

MOD = 10**9+7

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

positive = []
negative = []

for a in A:
    if a > 0:
        positive.append(a)
    else:
        negative.append(-a)

ans = sum(positive)+sum(negative)

m = len(negative)

if m%2==1:
    ans -= 2*(min(min(positive), min(negative)))

print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

MOD = 10**9+7

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

positive = []
negative = []

for a in A:
    if a > 0:
        positive.append(a)
    else:
        negative.append(-a)

ans = sum(positive)+sum(negative)

if len(negative)%2==1:
    ans -= 2*(min(min(positive), min(negative)))

print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

MOD = 10**9+7

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

positive = []
negative = []
zeros = []

for a in A:
    if a > 0:
        positive.append(a)
    elif a < 0:
        negative.append(-a)
    else:
        zeros.append(a)

ans = sum(positive)+sum(negative)

if len(zeros)==0 and len(negative)%2==1:
    ans -= 2*(min(min(positive), min(negative)))

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=np.array([int(c) for c in input().split()])
AP=A[A>=0]
AN=A[A<0]
if(len(AN)%2==1):
  print(max(-sum(AN)+2*max(AN)+sum(AP),-sum(AN)-2*min(AP)+sum(AP)))
else:
  print(-sum(AN)+sum(AP))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n=int(input())
    aa=LI()
    pp=[]
    mm=[]
    for a in aa:
        if a<0:mm.append(a)
        else:pp.append(a)
    if len(mm)%2:
        m=max(mm)
        p=min(pp)
        if p+m>=0:print(sum(pp)-sum(mm)+2*m)
        else:print(sum(pp)-2*p-sum(mm))
    else:
        print(sum(pp)-sum(mm))

main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
absA = [abs(i) for i in A]
minusA = [i for i in A if i<0]
mina = min(absA)
if (0 in A) or (len(minusA)%2 == 0):
    print(sum(absA))
else:
    print(absA -2*mina)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

n = int(input())
a = tuple(sorted(map(int, input().split())))
j = bisect_left(a, 0)

p = a[j:]
m = a[:j]

if len(m) % 2 == 0:
    print(sum(p) - sum(m))
else:
    print(sum(p[1:]) - sum(m[:-1]) + abs(p[0] + m[-1]))

Submission status: Runtime Error

Solution code:
n=input()
a=list(map(int,input().split()))
n=sum(x<0 for x in a)
a=[map(abs,a)]
s=sum(a) if n%2==0 else sum(a)-min(a)*2
print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=list(map(lambda x: abs(x),a))
neg_sum=sum(x<0 for x in a)
m = min(a)
s=sum(a)
s-=m if neg_sum%2
print(s)

Submission status: Runtime Error

Solution code:
#(ai,ai+1),(ai+1,ai+2)...(aj-1,aj)に-1を掛けると
#ai,ajに-1を掛けることができる

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

mns = [ai for ai in a if ai<0]
pls = [ai for ai in a if ai>=0]

mns.sort()
pls.sort()

lm = len(mns)
m_rem = 0
if lm%2:
    if pls[0]<-1*mns[-1]:
        tmp = -1*mns[-1]
        mns[-1] = -1*pls[0]
        pls[0] = tmp
    m_rem = mns.pop()

print(sum(pls)-sum(mns) + m_rem)

Submission status: Runtime Error

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

def solve(a):
    if len(a) == 0:
        return 0
    elif len(a) == 1:
        return a[0]
    elif len(a) == 2:
        v1 = a[0] + a[1]
        v2 = -a[0] - a[1]
        return max(v1, v2)

    v1 = a[0] + solve(a[1:])
    v2 = -a[0] + solve([-a[1]] + a[2:])
    return max(v1, v2)

# for i in range(n-1):
#     v1 = a[i] + a[i+1]
#     v2 = -a[i] - a[i+1]
#     if v2 > v1:
#         a[i] = -a[i]
#         a[i+1] = -a[i+1]

# print(a)
# print(sum(a))

print(solve(a))

Submission status: Runtime Error

Solution code:
a=int(input())
lis=list(map(int,input().split()))
lis=sorted(lis)
i=0
while lis[i]<0 and i<a-1:
  if lis[i]<=0 and lis[i+1]>=0:
    if -1*lis[i]>lis[i+1]:
      lis[i],lis[i+1]=-lis[i],-lis[i+1]
  elif lis[i]<=0 and lis[i+1]<=0:
    lis[i],lis[i+1]=-lis[i],-lis[i+1]
  i+=2
print(sum(lis))

Submission status: Runtime Error

Solution code:
a=int(input())
lis=list(map(int,input().split()))
lis=sorted(lis)
i=0
while lis[i]<0:
  if lis[i]<=0 and lis[i+1]>=0:
    if -1*lis[i]>lis[i+1]:
      lis[i],lis[i+1]=-lis[i],-lis[i+1]
  elif lis[i]<=0 and lis[i+1]<=0:
    lis[i],lis[i+1]=-lis[i],-lis[i+1]
  i+=2
print(sum(lis))

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop

N = int(input())
array = list(map(int,input().split()))
nega = []
posi = []

for num in array:
  if num >= 0:
    heappush(posi,num)
  else:
    heappush(nega,num)

nega = [num*(-1) for num in nega]

if len(nega)%2==0:
  ans = sum(nega) + sum(posi)
else:
  min_posi = heappop(posi)
  max_nega = heappop(nega)
  if min_posi > max_nega:
    ans = sum(nega) + sum(posi) + min_posi - max_nega
  else:
    ans = sum(nega) + sum(posi) - min_posi + max_nega
    
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, t = LI()
    print(b * (t // a))
    return

#B
def B():
    n = II()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += v[i] - c[i]
    print(ans)
    return

#C
def C():
    def gcd(a, b):
        if b > a: a, b = b, a
        while b:
            a, b = b, a % b
        return a
    n = II()
    a = LI()
    dp1 = [None] * (n - 1)
    dp1[0] = a[0]
    dp2 = [None] * (n - 1)
    dp2[-1] = a[-1]
    for i in range(1, n - 1):
        dp1[i] = gcd(dp1[i - 1], a[i])
        dp2[-i - 1] = gcd(dp2[-i], a[-i - 1])
    ans = 0
    dp1.insert(0, dp2[0])
    dp2.append(dp1[-1])
    for i in range(n):
        ans = max(ans, gcd(dp1[i], dp2[i]))
    print(ans)
    return

#D
def D():
    n = II()
    a = LI()
    positive = []
    negative = []
    for ai in a:
        if ai >= 0:
            positive.append(ai)
        else:
            negative.append(ai)
    positive.sort()
    negative.sort()
    ans = sum(positive) + sum(map(lambda x: abs(x), negative))
    if len(negative) & 1:
        ans -= 2 * min(positive[0], abs(negative[-1]))
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=list(map(lambda x:-x if x < 0 else x, A))
A.sort()
print(sum(A[1:]-A[0]))

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int, input().split()))
A=list(map(math.fabs, A))
A.sort()
print(sum(A[1:]-A[0]))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=list(map(abs, A))
A.sort()
print(sum(A[1:]-A[0]))

Submission status: Runtime Error

Solution code:
N=int(input())
l=list(map(int,input().split()))
l2=sorted([num for num in l if num<0])
l3=sorted([num for num in l if num>=0])
if len(l2)%2==0:
  ans=sum([abs(n) for n in l])

else:
  if abs(l2[-1]) < l3[1]:
    x=l2.pop()
  else:
    x=l3.pop(0)
  ans=sum([abs(n) for n in l2])+sum(l3)-abs(x)
print(ans)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
A = [int(i) for i in input().split(' ')]

# 1 から N-1 を小さい順に並べる
# 負の数が残り1つになるまで -1 を掛ける操作を繰り返す
# 最後の負の数になったときに、足してマイナスになるなら -1 を掛ける

A_n_1 = sorted(copy.deepcopy(A[:-1]))
An = A[-1]

is_N_minus = True if An < 0 else False
An_abs = abs(An)

result = 0
for i in range(N - 1):
    if A_n_1[i] <= 0:
        if A_n_1[i + 1] > 0:
            # 判断する
            _an = An_abs
            _an_pm = -1 if is_N_minus else 1
            _an = _an_pm * _an
            if A_n_1[i] + _an < 0:
                is_N_minus = not is_N_minus  # An に -1 を掛ける
                result += -A_n_1[i]  # ー1 をかけて足す
            else:
                result += A_n_1[i]
        else:
            is_N_minus = not is_N_minus  # An に -1 を掛ける
            result += -A_n_1[i]  # ー1 をかけて足す
    else:
        result += A_n_1[i]

# N番目を足す
_an = An_abs
_an_pm = -1 if is_N_minus else 1
_an = _an_pm * _an
result += _an

print(result)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    tmp = float("inf")
    S = 0
    count = 0
    for i in A:
        if tmp > abs(A[i]):
            tmp = abs(A[i])
        if abs(A[i]) != A[i]:
            count += 1
        S += abs(A[i])
    if count%2 == 0:
        print(S)
    else:
        print(S-2*tmp)
    
main()

Submission status: Runtime Error

Solution code:
N=int(input())
A = [int(i) for i in input().split()]
cnt=0
ans=0
B=[]
for i in range(N):
    if A[i]<0:
        cnt+=1
if cnt%2==0:
    ans=sum(abs(A))
    print(ans)
else:
    for i in range(N):
        if A[i]<0:
            B.append(A[i])
    max(B)
    ans=sum(abs(A))
    ans=ans+2*B
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
a_s=sorted(a)
for i in range(0,n,2):
    if a_s[i]<0 and a_s[i+1]<0:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    elif a_s[i]<0 and -a_s[i]>a_s[i+1]:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    else:
        break
print(sum(a_s))

Submission status: Runtime Error

Solution code:
import itertools

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

n=getint()
a=getints()
inf = 1 << 60

cache=[[-inf] * 2 for _ in range(n)]

def solve(pos, minus):
    if pos == n - 1:
        return -a[pos] if minus else a[pos]
    res = cache[pos][minus]
    if res > -inf:
        return res
    now = a[pos] if minus == 0 else -a[pos]
    res1 =  now + solve(pos + 1, 0)
    res2 = -now + solve(pos + 1, 1)
    res  = max(res1, res2)
    cache[pos][minus] = res
    return res

res = solve(0, 0)
print(res)

Submission status: Runtime Error

Solution code:
n = int(input())
li = list(map(int, input().split()))
temp = li.copy()
for i in range(n-1):
    if li[i] < 0:
        li[i] *= -1
        li[i+1] *= -1
ans = sum(li)
li = temp
for i in reversed(range(1,n)):
    if li[i] < 0:
        li[i] *= -1
        li[i+1] *= -1
ans = max(ans, sum(li))

Submission status: Runtime Error

Solution code:


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

    def dp(i, j):
        if i == 0 and j == 0:
            return 0
        if i == 0 and j == 1:
            return -float('inf')
        if j == 0:
            return max(dp(i - 1, 0) + a[i - 1], dp(i - 1, 1) - a[i - 1])
        if j == 1:
            return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])

    score = dp(n, 0)

    print(score)


main()

Submission status: Runtime Error

Solution code:
import bisect
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
idx = bisect.bisect_left(A,0)
if idx%2 == 0:
  ans = abs(sum(A[0:idx])) + sum(A[idx:])
else:
  ans = abs(sum(A[0:idx-1])) + abs(A[idx-1]+A[idx]) + sum(A[idx+1:])
print(ans)

Submission status: Runtime Error

Solution code:
-*- using:utf-8 -*-

def count_negative(n,a):
    count = 0
    for i in range(n):
        if a[i] == 0:
            return 0
        elif a[i] < 0:
            count += 1
    return count

def num_of_min(n,a):
    minimum = max(a)
    count = 0
    tmp = 0
    for i in range(n):
        tmp = abs(a[i])
        if tmp < minimum:
            minimum = tmp
            count = i
        else:
            pass
    return count

def flipping(n,a):
    nc = count_negative(n,a)
    total = 0
    count = 0
    if nc % 2 == 0:
        for i in range(n):
            total += abs(a[i])
    else:
        count = num_of_min(n,a)
        target = a.pop(count)

        k = n - 1
        for i in range(k):
            total += abs(a[i])
        else:
            total += target*(-1)

    return total

if __name__ == '__main__':
    n = int(raw_input())
    a = map(int,raw_input().split())
    gt = flipping(n,a)
    print("%d" %gt)

Submission status: Runtime Error

Solution code:
-*- using:utf-8 -*-

def count_negative(n,a):
    count = 0
    for i in range(n):
        if a[i] == 0:
            return 0
        elif a[i] < 0:
            count += 1
    return count

def num_of_min(n,a):
    minimum = max(a)
    count = 0
    tmp = 0
    for i in range(n):
        tmp = abs(a[i])
        if tmp < minimum:
            minimum = tmp
            count = i
        else:
            pass
    return count

def flipping(n,a):
    nc = count_negative(n,a)
    total = 0
    count = 0
    if nc % 2 == 0:
        for i in range(n):
            total += abs(a[i])
    else:
        count = num_of_min(n,a)
#            print("i %d, a[i] %d, count %d" %(i,a[i],count))
        target = a.pop(count)

        k = n - 1
        for i in range(k):
            total += abs(a[i])
#            print("i %d, tmp total %d" %(i,total))
        else:
            total += target*(-1)

    return total

if __name__ == '__main__':
    n = int(raw_input())
    a = map(int,raw_input().split())
    gt = flipping(n,a)
    print("%d" %gt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
for _ in range(n):
  if a[_]<0:
    b.append(a.pop(_)*(-1))
if 0 in a or len(b)%2==0:
  print(sum(a)+sum(b))
else:
  b.sort()
  print(sum(a)+sum(b)-(b[0]*2))