Problem:


Score : 300 points

Problem Statement

You are given an integer sequence of length N. The i-th term in the sequence is a_i.
In one operation, you can select a term and either increment or decrement it by one.

At least how many operations are necessary to satisfy the following conditions?

For every i (1≤i≤n), the sum of the terms from the 1-st through i-th term is not zero.

For every i (1≤i≤n-1), the sign of the sum of the terms from the 1-st through i-th term, is different from the sign of the sum of the terms from the 1-st through (i+1)-th term.

Constraints

2 ≤ n ≤ 10^5

|a_i| ≤ 10^9

Each a_i is an integer.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_n

Output

Print the minimum necessary count of operations.

Sample Input 1

4
1 -3 1 0

Sample Output 1

4

For example, the given sequence can be transformed into 1, -2, 2, -2 by four operations. The sums of the first one, two, three and four terms are 1, -1, 1 and -1, respectively, which satisfy the conditions.

Sample Input 2

5
3 -6 4 -5 7

Sample Output 2

0

The given sequence already satisfies the conditions.

Sample Input 3

6
-1 4 3 2 -5 4

Sample Output 3

8



Sample input:
4
1 -3 1 0


Sample output:
4

Submission status: Wrong Answer

Solution code:
def solve(N, A):
    a = A[0]
    ans = 0
    for i in xrange(1, N):
        if a > 0 and a + A[i] < 0:
            a = a + A[i]
        elif a > 0 and a + A[i] >= 0:
            ans += A[i] + a + 1
            a = -1
        elif a < 0 and a + A[i] > 0:
            a = a + A[i]
        else:
            ans += -(A[i]+a)+1
            a = 1
    return ans


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

if A[0] == 0:
    A[0] = -1
    ans1 = solve(N, A) + 1
    A[0] = 1
    ans2 = solve(N, A) + 1
    print min(ans1, ans2)
else:
    print solve(N, A)

Submission status: Wrong Answer

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

if a[0]==0:
	if a[1]>0:
		a[0]=-1
	else:
		a[0]=1
	ans+=1

if a[0]>0:
	mode=0#if i+1%2==0, above 0
else:
	mode=1
sumA=a[0]
#print(sumA)
for i in range(1,N):
	#above 0
	sumA+=a[i]
	if (i+mode)%2==0:
		if sumA<=0:
			ans-=(sumA-1)
			sumA=1
	else:
		if sumA>=0:
			ans+=(sumA+1)
			sumA=-1
	#print(sumA)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = [int(_) for _ in raw_input().split()]
ans = 0
t = a[0]
for i in xrange(1, n):
    b = cmp(t, 0)
    t += a[i]
    c = cmp(t, 0)
    d = 0
    if b == c or c == 0:
        d = -t - 1 if b == 1 else -t + 1
        ans += abs(d)
        t += d

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def solve(a):
    s, res = 0, 0
    for i, ai in enumerate(a):
        ss = s
        ss += ai
        if ss == 0:
            ss = 1 if s < 0 else -1
            res += 1
        else:
            if s < 0 and ss < 0:
                res += abs(ss) + 1
                ss = 1
            if s > 0 and ss > 0:
                res += abs(ss) + 1
                ss = -1
        s = ss
    return res

n = int(raw_input())
a = map(int, raw_input().split()) 

if a[0] == 0:
    a[0] = 1
    ans = solve(a)
    a[0] = -1
    ans = min(ans, solve(a))
else:
    ans = solve(a)

print ans

Submission status: Wrong Answer

Solution code:
N = int( input() )
A = list( map( int, input().split() ) )
ans = 0
if A[ 0 ] == 0:
  A[ 0 ] = -1
  s = A[ 0 ]
  f = 0
  for i in range( 1, N, 1 ):
    ns = s + A[ i ]
    if ns * s >= 0:
      ns = s // abs( s ) * -1
      f += abs( ns - ( s + A[ i ] ) )
    s = ns
  A[ 0 ] = 1
  s = A[ 0 ]
  g = 0
  for i in range( 1, N, 1 ):
    ns = s + A[ i ]
    if ns * s >= 0:
      ns = s // abs( s ) * -1
      g += abs( ns - ( s + A[ i ] ) )
    s = ns
  ans = max( f, g ) + 1
else:
  s = A[ 0 ]
  for i in range( 1, N, 1 ):
    ns = s + A[ i ]
    if ns * s >= 0:
      ns = s // abs( s ) * -1
      ans += abs( ns - ( s + A[ i ] ) )
    s = ns
print( ans )

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
ans=0
su=a[0]
for i in xrange(1,n):
    tmp=su
    su+=a[i]
    if su*tmp<0:
        continue
    else:
        if su==0 and tmp<0:
            ans+=1
            su+=1
        elif su==0 and tmp>0:
            ans+=1
            su-=1
        elif tmp<0 and su<0:
            ans+=-su+1
            su=1
        elif tmp>0 and su>0:
            ans+=su+1
            su=-1
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(raw_input())
a = map(int, raw_input().split()) 

s, ans = 0, 0
for i, ai in enumerate(a):
    ss = s
    ss += ai
    if ss == 0:
        if i < n - 1:
            ss = -1 if a[i + 1] >= 0 else 1
        else:
            ss = 1
        ans += 1
    else:
        if 0 < s and 0 < ss:
            ans += ss + 1
            ss = -1
        if s < 0 and ss < 0:
            ans += abs(ss) + 1
            ss = 1
    s = ss

print ans

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ct = 0
for x in range(n-1):
    i, j = sum(a[:x+1]), sum(a[:x+2])
    if (i >= 0 and j >= 0) or (i < 0 and j < 0):
        f = j-1 if j < 0 else j+1
        a[x+1] -= f
        ct += abs(f)
print(ct if sum(a) else ct+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = a[0]
ans = 0
for x in a[1:]:
    prev = s
    s += x
    while prev * s >= 0:
        ans += 1
        s += 1 if prev < 0 else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N=int(input())

A=list(map(int,input().split()))
AP=copy.copy(A)
AM=copy.copy(A)
ansP=0
for i in range(N):
    if i%2==1:
        if sum(AP[:i+1])>=0:
            #print(i,AP)
            a=sum(AP[:i+1])
            ansP+=(a+1)
            AP[i]-=(abs(a)+1)
    else:
        if sum(AP[:i+1])<=0:
            #print(i,AP)
            a=sum(AP[:i+1])
            ansP+=(abs(a)+1)
            AP[i]+=(abs(a)+1)
#print(AP)
ansM=0
for i in range(N):
    if i%2==0:
        if sum(A[:i+1])>=0:
            a=sum(A[:i+1])
            ansM+=(abs(a)+1)
            A[i]-=(abs(a)+1)
    else:
        if sum(A[:i+1])<=0:
            a=sum(A[:i+1])
            ansM+=(abs(a)+1)
            A[i]+=(abs(a)+1)
#print(A)
print(min(ansP,ansM))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

a=list(map(int,input().split()))
A=[]
B=[]
for x in range(len(a)):
    A.append(a[x])
    B.append(a[x])
    
start_is_plus=0
if A[0]<=0:
    start_is_plus+=(1-A[0])
    A[0]=1

for i in range(1,len(A)):
    if i%2==1:
        if sum(A[:i+1])>=0:
            start_is_plus+=(sum(A[:i+1])+1)
            A[i]-=(sum(A[:i+1])+1)
    else:
        if sum(A[:i+1])<=0:
            start_is_plus+=(1-sum(A[:i+1]))
            A[i]+=(1-sum(A[:i+1]))
#print(A)  
start_is_minus=0
if B[0]>=0:
    start_is_minus+=(B[0]+1)
    B[0]=(-1)
    
for j in range(1,len(B)):
    if j%2==1:
       if sum(B[:j+1])<=0:
            start_is_minus+=(1-sum(B[:j+1]))
            B[j]+=(1-sum(B[:j+1]))
    else:
        if sum(B[:j+1])>=0:
            start_is_minus+=(sum(B[:j+1])+1)
            B[j]-=(sum(B[:j+1])+1) 
#print(B)
print(min(start_is_minus,start_is_plus))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def osilate(seq):
    flag = 1
    acc = 0
    ans = 0
    #while loop O(n)
    while len(seq) > 0:
        a = seq[0]
        acc += a

        if flag > 0:
            if acc <= 0:
                ans += 1-acc
                acc = 1
        if flag < 0:
            if acc >= 0:
                ans += 1+acc
                acc = -1
        #print(seq, acc, ans)
        seq.pop(0)
        flag = flag * (-1)
    return ans

n = int(input()) #(1)
seq = [int(i) for i in input().split()] #O(N)

seq_rev = [-i for i in seq]  # O(N)
print(min(osilate(seq),osilate(seq_rev))) #O(2N)

Submission status: Time Limit Exceeded

Solution code:
def osilate(seq):
    flag = 1
    acc = 0
    ans = 0
    while len(seq) > 0:

        a = seq[0]
        acc += a

        if flag > 0:
            if acc <= 0:
                ans += 1-acc
                acc = 1
        if flag < 0:
            if acc >= 0:
                ans += 1+acc
                acc = -1
        #print(seq, acc, ans)
        seq.pop(0)
        flag = flag * (-1)
    return ans

n = int(input())
seq = [int(i) for i in input().split()]
acc = []
tmp = 0

seq_rev = [-i for i in seq]
print(min(osilate(seq),osilate(seq_rev)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def osilate(acc):
    acc = np.array(acc)
    flag = 1
    ans = 0
    while len(acc) > 0:
        #print(acc)
        a = acc[0]
        if flag > 0:
            if a <= 0:
                ans += 1-a
                acc = acc + (1-a)
        if flag < 0:
            if a >= 0:
                ans += 1+a
                acc = acc - (1+a)
        acc = acc[1:]
        flag = flag * (-1)
    return ans

n = int(input())
seq = [int(i) for i in input().split()]
acc = []
tmp = 0
for i in seq:
    tmp += i
    acc.append(tmp)
acc_rev = [-i for i in acc]

print(min(osilate(acc),osilate(acc_rev)))

Submission status: Time Limit Exceeded

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

total1 = 0
total2 = 0
count1 = 0
count2 = 0
roop = 1
guki = 0

for i in a:
    guki = roop % 2
    if(roop == 1):
        total1 = i
        total2 = i
        roop += 1
        continue

    total1 += i
    total2 += i

    if(guki == 0):
        if(total1 >= 0):
            while(total1>=0):
                count1 += 1
                total1 -= 1
        if(total2 <= 0):
            while(total2<=0):
                count2 += 1
                total2 += 1
    elif(guki == 1):
        if(total1 <= 0):
            while(total1<=0):
                count1 += 1
                total1 += 1
        if(total2 >= 0):
            while(total2>=0):
                count2 += 1
                total2 -= 1

    roop += 1

if(count1 >= count2):
    print(count2)
else:
    print(count1)

Submission status: Time Limit Exceeded

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

counter = 0
prev = a[0] * -1
for idx in range(n):
    s = sum(a[:idx+1])

    if prev * s > 0:
        if s < 0:
            while s < 1:
                s += 1
                a[idx] += 1
                counter += 1
        elif s > 0:
            while s > -1:
                s -= 1
                a[idx] -= 1
                counter += 1
    elif s == 0:
        if prev > 0:
            s -= 1
            counter += 1
        elif prev < 0:
            s += 1
            counter += 1

    prev = s

print counter

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """
        (a0+a1+...+ai < x となる最大の i (存在しない時は -1 ) , その時の a0+a1+...+ai )
        a0+a1+...+ai <= x としたい場合は equal = True
        二分探索であるため、ai>=0 を満たす必要がある
        """
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

###############################################################
def solve(sign):
    B = Bit(N)
    B.built(A)
    res = 0
    for i in range(N):
        tmp = B.sum(i + 1)
        if tmp * sign > 0:
            B.add(i, -1 * sign * (abs(tmp) + 1))
            res += abs(tmp) + 1
        elif tmp == 0:
            B.add(i, -1 * sign)
            res += 1
        sign *= -1
    return res

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
print(min(solve(-1), solve(1)))

Submission status: Accepted

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

s1=0
now=0
for i in range(n):
    now+=A[i]
    if i%2==1 and now<=0:
        s1+= (1-now)
        now=1
    if i%2==0 and now>=0:
        s1+= now+1
        now=-1

s2=0
now=0
for i in range(n):
    now+=A[i]
    if i%2==0 and now<=0:
        s2+= (1-now)
        now=1
    if i%2==1 and now>=0:
        s2+= now+1
        now=-1
print(min(s1,s2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c1=0
s=0
for i in range(n):
  s+=a[i]
  if i%2:
    if s>=0:
      c1+=s+1
      s=-1
  else:
    if s<=0:
      c1+=-s+1
      s=1
c2=0
s=0
for i in range(n):
  s+=a[i]
  if i%2:
    if s<=0:
      c2+=-s+1
      s=1
  else:
    if s>=0:
      c2+=s+1
      s=-1
print(min(c1,c2))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())


for i in range(1,n):
    a[i] += a[i-1]

aa = a[:]

sgn = 1
r1 = 0
v = 0
for i in range(n):
    a[i] += v
    if sgn:
        if a[i] <= 0:
            r1 += -a[i]+1
            v += -a[i]+1
    else:    
        if a[i] >= 0:
            r1 += a[i]+1
            v -= a[i]+1
    sgn ^= 1
    

a = aa
sgn = 0
r2 = 0
v = 0
for i in range(n):
    a[i] += v
    if sgn:
        if a[i] <= 0:
            r2 += -a[i]+1
            v += -a[i]+1
    else:    
        if a[i] >= 0:
            r2 += a[i]+1
            v -= a[i]+1
    sgn ^= 1

#print(r1,r2)
print(min(r1,r2))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    s = 0
    c1 = 0
    for i, a in enumerate(A):
        s += a
        if i % 2 == 0:
            if s == 0:
                c1 += 1
            elif s < 0:
                c1 += 1 - s
            else:
                continue
            s = 1
        else:
            if s == 0:
                c1 += 1
            elif s > 0:
                c1 += s + 1
            else:
                continue
            s = -1
    s = 0
    c2 = 0
    for i, a in enumerate(A):
        s += a
        if i % 2 != 0:
            if s == 0:
                c2 += 1
            elif s < 0:
                c2 += 1 - s
            else:
                continue
            s = 1
        else:
            if s == 0:
                c2 += 1
            elif s > 0:
                c2 += s + 1
            else:
                continue
            s = -1
    print(min(c1, c2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def func(alst, sign):
  cur, res = 0, 0
  for i in alst:
    cur += i
    if sign and cur <= 0:
      res += abs(cur) + 1
      cur = 1
    elif not sign and cur >= 0:
      res += abs(cur) + 1
      cur = -1
    sign = not sign
  return res


def main():
  n, *alst = map(int, sys.stdin.read().split())
  print(min(func(alst, True), func(alst, False)))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
A=int(input())
l=list(map(int,input().split()))
sum_n=0
ans=0
caseA=0
for i in range(A):
   sum_n+=l[i]
   if i%2==0:
      if 0<sum_n:
         continue
      else:
         ans+=abs(1-sum_n)
         sum_n=1
   else:
      if sum_n < 0:
         continue
      else:
         ans+=abs(-1-sum_n)
         sum_n=-1
caseA=ans
ans=0
sum_n=0
for i in range(A):
   sum_n+=l[i]
   if i%2==1:
      if 0<sum_n:
         continue
      else:
         ans+=abs(1-sum_n)
         sum_n=1
   else:
      if sum_n < 0:
         continue
      else:
         ans+=abs(-1-sum_n)
         sum_n=-1
print(min(ans,caseA))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = [0,0]

s = max(a[0],1)
ans[0] = abs(s-a[0])
for i in range(n-1):
    if s * (s + a[i+1]) >= 0:
        if s > 0:
            ans[0] += s + a[i+1] + 1
            s = -1
        else:
            ans[0] += 1 - (s + a[i+1])
            s = 1
    else:
            s += a[i+1]
s = min(-1,a[0])
ans[1] = abs(s-a[0])
for i in range(n-1):
    if s * (s + a[i+1]) >= 0:
        if s > 0:
            ans[1] += s + a[i+1] + 1
            s = -1
        else:
            ans[1] += 1 - (s + a[i+1])
            s = 1
    else:
            s += a[i+1]
print(min(ans))

Submission status: Accepted

Solution code:
n = int(input())

arr = [int(x) for x in input().split(" ")]

ans = 0

sum = 0

curr = True

for i in range(len(arr)):
    if ((sum + arr[i]) == 0 or ((sum + arr[i]) > 0) == curr):
        if curr:
            temp = -1 - sum
        else:
            temp = 1 - sum
        ans += abs(temp - arr[i])
        sum += temp
    else:
        sum += arr[i]
    curr = not curr

ans1 = 0

curr = False

sum = 0

for i in range(len(arr)):
    if ((sum + arr[i]) == 0 or ((sum + arr[i]) > 0) == curr):
        if curr:
            temp = -1 - sum
        else:
            temp = 1 - sum
        ans1 += abs(temp - arr[i])
        sum += temp
    else:
        sum += arr[i]
    curr = not curr

print(min(ans,ans1))

Submission status: Accepted

Solution code:
N, = map(int, input().split())
A = list(map(int, input().split()))
s = 0
r = 0
for i, a in enumerate(A):
    s += a
    if i % 2:
        if s >= 0:
            r += s+1
            s = -1
    else:
        if s <= 0:
            r += -s+1
            s = 1
s = 0
r2 = 0
for i, a in enumerate(A):
    s += a
    if i % 2:
        if s <= 0:
            r2 += -s+1
            s = 1
    else:
        if s >= 0:
            r2 += s+1
            s = -1
print(min(r, r2))

Submission status: Accepted

Solution code:
import copy

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

def f(org_a, odd):
    a = copy.copy(org_a)
    ans = 0
    if a[0] == 0:
        a[0] = 1 if odd else -1
        ans += 1
    elif a[0] > 0 and not odd:
        ans += a[0] + 1
        a[0] = -1
    elif a[0] < 0 and odd:
        ans += -a[0] + 1
        a[0] = 1
    current_sum = a[0]
    for i in range(1, len(a)):
        move = 0
        is_positive = current_sum > 0
        current_sum += a[i]
        if is_positive and current_sum >= 0:
            move = -current_sum - 1
        elif not is_positive and current_sum <= 0:
            move = -current_sum + 1

        current_sum += move
        # print(current_sum)
        a[i] += move
        ans += abs(move)
    return ans

# print(a)
print(min(f(a, True), f(a, False)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    s1, s2 = 0, 0
    c1, c2 = 0, 0
    for i in range(N):
        if i % 2 == 0:
            if s1 + A[i] > 0:
                s1 += A[i]
            else:
                c1 += abs(s1 + A[i]) + 1
                s1 = 1
            if s2 + A[i] < 0:
                s2 += A[i]
            else:
                c2 += abs(s2 + A[i])+1
                s2 = -1
        else:
            if s1 + A[i] < 0:
                s1 += A[i]
            else:
                c1 += abs(s1 + A[i]) + 1
                s1 = -1
            if s2 + A[i] > 0:
                s2 += A[i]
            else:
                c2 += abs(s2 + A[i]) + 1
                s2 = 1
    print(min(c1, c2))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

N = int(input())
a = list(map(int,input().split()))
# >0
r = 0
res = 0
for i in range(N):
    sa = 0
    r += a[i]
    if i%2==0:
        if r <= 0:
            sa = 1-r
            r += sa
    else:
        if r >= 0:
            sa = r+1
            r -= sa
    res += sa

# <0
r = 0
res2 = 0
for i in range(N):
    sa = 0
    r += a[i]
    if i%2==1:
        if r <= 0:
            sa = 1-r
            r += sa
    else:
        if r >= 0:
            sa = r+1
            r -= sa
    res2 += sa
print(min(res,res2))

Submission status: Accepted

Solution code:
# ARC072C - Sequence (ABC059C)
def modify_seq(seq: list, is_positive: bool) -> int:
    cur, cnt = 0, 0
    for i in seq:
        cur += i
        if is_positive and cur <= 0:
            cnt += abs(cur) + 1
            cur = 1
        elif not is_positive and cur >= 0:
            cnt += abs(cur) + 1
            cur = -1
        is_positive = not is_positive
    return cnt


def main():
    _, *A = map(int, open(0).read().split())
    print(min(modify_seq(A, True), modify_seq(A, False)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int, input().rstrip().split()))
# start with positive number
cur, cnt_1 = 0, 0
for i, j in enumerate(lst):
    new = cur + j
    if i % 2 == 0 and new <= 0:
        cnt_1 += abs(new) + 1
        cur = 1
    elif i % 2 == 1 and new >= 0:
        cnt_1 += abs(new) + 1
        cur = -1
    else:
        cur = new

# start with negative number
cur, cnt_2 = 0, 0
for i, j in enumerate(lst):
    new = cur + j
    if i % 2 == 0 and new >= 0:
        cnt_2 += abs(new) + 1
        cur = -1
    elif i % 2 == 1 and new <= 0:
        cnt_2 += abs(new) + 1
        cur = 1
    else:
        cur = new
print(min(cnt_1, cnt_2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
now = a[0]
if now == 0:
  ans = 1
  now = 1
else:
  ans = 0
for i in a[1:]:
  t = now + i
  if now * t >= 0:
    if now >= 0:
      ans += t + 1
      now = -1
    else:
      ans += 1 - t
      now = 1
  else:
    now = t
    
if a[0] >= 0:
  now = -1
  ans2 = a[0] - now
else:
  now = 1
  ans2 = now - a[0]
for i in a[1:]:
  t = now + i
  if now * t >= 0:
    if now >= 0:
      ans2 += t + 1
      now = -1
    else:
      ans2 += 1 - t
      now = 1
  else:
    now = t
ans = min(ans,ans2)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# greedy,2通りやる

N,*A = map(int,read().split())

def solve(A):
    # A[0] > 0 となるように
    cum = 0
    cnt = 0
    for x in A:
        if cum <= 0:
            # positiveにしたい
            cum += x
            if cum <= 0:
                cnt += (1 - cum)
                cum = 1
        else:
            # negativeにしたい
            cum += x
            if cum >= 0:
                cnt += (1 + cum)
                cum = -1
    return cnt

x = solve(A)
y = solve([-x for x in A])
answer = min(x,y)
print(answer)

Submission status: Accepted

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

def cost(a, neg=False):
    sign = -1 if neg else 1
    if sign * a[0] > 0:
        ret = 0
        cum = a[0]
    else:
        ret = abs(a[0] - sign)
        cum = sign
    for i in range(1, n):
        sign *= -1
        cum += a[i]
        if cum * sign > 0:
            continue
        else:
            ret += abs(cum - sign)
            cum = sign
    return ret

print(min(cost(a, False), cost(a, True)))

Submission status: Accepted

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

# s[0]>0のとき
s=0
anse=0
for i in range(n):
    s+=a[i]
    if i%2==0 and s<=0:
        anse+=1-s
        s=1
    elif i%2==1 and s>=0:
        anse+=s+1
        s=-1

# s[0]<0のとき
s=0
anso=0
for i in range(n):
    s+=a[i]
    if i%2==0 and s>=0:
        anso+=s+1
        s=-1
    elif i%2==1 and s<=0:
        anso+=1-s
        s=1

ans=min(anse,anso)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a = list(map(int,input().split()))
    sp=0
    sm=0
    cntp=0
    cntm=0
    for i in range(n):
        sp+=a[i]
        sm+=a[i]
        if abs(sp)>=1 and sp//(abs(sp))==(-1)**i:
            sp+=0
        else:
            cntp+=abs(sp)+1
            sp=(-1)**i
        if abs(sm)>=1 and sm//(abs(sm))==(-1)**(i+1):
            sm+=0
        else:
            cntm+=abs(sm)+1
            sm=(-1)**(i+1)
    print(min(cntp,cntm))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
 
ans = 0

def func(l, pn):
  ans = 0
  sum_ = 0
  for i in range(n):
    sum_ += l[i]
    if sum_ >= 0 and pn[i] < 0:
      ans += sum_+1
      sum_ = -1
    elif sum_ <= 0 and pn[i] > 0:
      ans += -sum_+1
      sum_ = 1
    else:
      continue
  return ans

pn1 = [1 if i%2 == 0 else -1 for i in range(n)]
pn2 = [-1 if i%2 == 0 else 1 for i in range(n)]

print(min(func(l, pn1), func(l, pn2)))

Submission status: Accepted

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

s = ans1 = 0
for i,a in enumerate(A):
    s += a
    if i%2:
        if s <= 1:
            ans1 += 1-s
            s = 1
    else:
        if s >= -1:
            ans1 += s+1
            s = -1

s = ans2 = 0
for i,a in enumerate(A):
    s += a
    if i%2==0:
        if s <= 1:
            ans2 += 1-s
            s = 1
    else:
        if s >= -1:
            ans2 += s+1
            s = -1

print(min(ans1,ans2))

Submission status: Accepted

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

pos = 0
now = 0
for i, a in enumerate(A):
    now += a
    if i % 2 == 0:  # poisive
        if now <= 0:
            pos += -now + 1
            now = 1
    else:
        if now >= 0:
            pos += now + 1
            now = -1

neg = 0
now = 0
for i, a in enumerate(A):
    now += a
    if i % 2 == 0:
        if now >= 0:
            neg += now + 1
            now = -1
    else:
        if now <= 0:
            neg += -now + 1
            now = 1

print(min(pos, neg))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = A.copy()
ans = [0, 0]
flag1 = True
flag2 = False
for i in range(0, N):
    if i != 0:
        A[i] += A[i-1]
    if flag1:
        if A[i] <= 0:
            ans[0] += (abs(A[i])+1)
            A[i] = 1
        flag1 = False
    else:
        if A[i] >= 0:
            ans[0] += (abs(A[i])+1)
            A[i] = -1
        flag1 = True
for i in range(0, N):
    if i != 0:
        B[i] += B[i-1]
    if flag2:
        if B[i] <= 0:
            ans[1] += (abs(B[i])+1)
            B[i] = 1
        flag2 = False
    else:
        if B[i] >= 0:
            ans[1] += (abs(B[i])+1)
            B[i] = -1
        flag2 = True
print(min(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int,input().split()))
    
    tmp = 0
    tmpans1 = 0
    for i in range(N):
        tmp += A[i]
        if i%2==0 and tmp<=0:
            tmpans1 += 1-tmp
            tmp = 1
        elif i%2==1 and tmp >= 0:
            tmpans1 += 1+tmp
            tmp = -1
    tmp = 0
    tmpans2 = 0
    for i in range(N):
        tmp += A[i]
        if i%2==0 and tmp>=0:
            tmpans2 += 1+tmp
            tmp = -1
        elif i%2==1 and tmp <= 0:
            tmpans2 += 1-tmp
            tmp = 1
    #print(tmpans1,tmpans2)
    print(min(tmpans1,tmpans2))
    
    
    
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int,input().split()))
    tmp_o = [0 for i in range(N+1)]
    tmp_e = [0 for i in range(N+1)]
    count_o = 0
    count_e = 0
    for i in range(N):
        tmp_o[i+1] = tmp_o[i]+A[i]
        if i%2 == 1 and tmp_o[i+1] <= 0:
            count_o += 1-tmp_o[i+1]
            tmp_o[i+1] = 1
        elif i%2 == 0 and tmp_o[i+1] >= 0:
            count_o += tmp_o[i+1]+1
            tmp_o[i+1] = -1
        else:
            continue
    for i in range(N):
        tmp_e[i+1] = tmp_e[i]+A[i]
        if i%2 == 0 and tmp_e[i+1] <= 0:
            count_e += 1-tmp_e[i+1]
            tmp_e[i+1] = 1
        elif i%2 == 1 and tmp_e[i+1] >= 0:
            count_e += tmp_e[i+1]+1
            tmp_e[i+1] = -1
        else:
            continue

    print(min(count_o,count_e))

if __name__ == "__main__":
    main()