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

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

def calc_sum(a, flag):
    ret = 0
    sum = 0
    for i in range(n):
        if (flag == 1 and sum + a[i] >= 0) or (flag == -1 and sum + a[i] <= 0):
            ret += abs(sum) + a[i] * flag + 1
            sum = -flag
        else:
            sum += a[i]
        flag = -flag
    return ret

print(min(calc_sum(a, 1), calc_sum(a, -1)))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

x = 0 #+-+-
y = 0 #-+-+
xx,yy = 0,0

for i in range(n):
    xx += a[i]
    yy += a[i]
    if not i%2:
        p = 0 if xx > 0 else 1-xx
        q = 0 if yy < 0 else 1+yy
        x += p
        y += q
        xx += p
        yy -= q
    else:
        p = 0 if yy > 0 else 1-yy
        q = 0 if xx < 0 else 1+xx
        y += p
        x += q
        yy += p
        xx -= q

print(min(x,y))

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
s=0
a=0
for i in range(n):
    s+=l[i]

    if i%2:
        if s<=0:
            a+=1-s
            s=1
    else:
        if s>=0:
            a+=s+1
            s=-1

b=0;s=0
for i in range(n):
    s+=l[i]
    if i%2==0:
        if s<=0:
            b+=1-s
            s=1
    else:
        if s>=0:
            b+=s+1
            s=-1
print(min(a,b))

Submission status: Accepted

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

s = [0,0]
ans = [0,0]
# [0]:+ - + - ... [1]:- + - + - ...

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
SUM = 0
cnt = 0
for i in range(n):
    SUM += a[i]
    if i % 2 == 0:
        cnt += max(0, 1 - SUM)
        SUM = max(1, SUM)
    else:
        cnt += max(0, 1 + SUM)
        SUM = min(-1, SUM)
ans = cnt

SUM = 0
cnt = 0
for i in range(n):
    SUM += a[i]
    if i % 2 == 0:
        cnt += max(0, 1 + SUM)
        SUM = min(-1, SUM)
    else:
        cnt += max(0, 1 - SUM)
        SUM = max(1, SUM)
ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

seq_sum = 0
sign = 1
count_1 = 0
for i in range(n):
    if A[i] * sign * (-1) > seq_sum * sign:
        seq_sum += A[i]
    else:
        count_1 += abs(sign * (-1) - (seq_sum + A[i]))
        seq_sum += A[i] + (sign * (-1) - (seq_sum + A[i]))
    sign = sign * (-1)

seq_sum = 0
sign = -1
count_2 = 0
for i in range(n):
    if A[i] * sign * (-1) > seq_sum * sign:
        seq_sum += A[i]
    else:
        count_2 += abs(sign * (-1) - (seq_sum + A[i]))
        seq_sum += A[i] + (sign * (-1) - (seq_sum + A[i]))
    sign = sign * (-1)

print(min(count_1, count_2))

Submission status: Accepted

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

ans = 0
f = 1
num = 0
for i in range(n):
    num += a[i]
    if f:
        if num <= 0:
            ans += 1 - num
            num = 1
        f = 0
    else:
        if num >= 0:
            ans += abs(-1 - num)
            num = -1
        f = 1

ans_2 = 0
f = 1
num = 0
for i in range(n):
    num += a[i]
    if f:
        if num >= 0:
            ans_2 += abs(-1 - num)
            num = -1
        f = 0
    else:
        if num <= 0:
            ans_2 += 1 - num
            num = 1
        f = 1

print(min(ans,ans_2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mulsum=[0]*n
cnt=0
cnt2=0
buf=0
cur=0
mulsum[0]=a[0]
for i in range(n-1):
    mulsum[i+1]=mulsum[i]+a[i+1]
#print(mulsum)
i=0
pm=[]
mp=[]
while i<n:#+-+-+-...の列を目指す
    if (mulsum[i]+buf)<=0:#a[i]+buf>0になるようbufを調整
        cur=mulsum[i]+buf
        buf=1-mulsum[i]
        cnt=cnt+(1-cur)
        #pm.append(1)
    else:
        i=i
        #pm.append(mulsum[i])
    if i==n-1:
        break
    if (mulsum[i+1]+buf)>=0:#a[i+1]+buf<0になるよう調整
        cur=mulsum[i+1]+buf
        buf=-1-mulsum[i+1]
        cnt=cnt+(1+cur)
        #pm.append(-1)
    else:
        i=i
        #pm.append(mulsum[i+1])
    i=i+2
#print(pm,cnt)
buf=0
i=0
while i<n:#-+-+-+...の列を目指す
    if (mulsum[i]+buf)>=0:#a[i]+buf<0になるようbufを調整
        cur=mulsum[i]+buf
        buf=-1-mulsum[i]
        cnt2=cnt2+(1+cur)
        #mp.append(-1)
    else:
        i=i
        #mp.append(mulsum[i])
    #print(buf,cnt2)
    if i==n-1:
        break
    if (mulsum[i+1]+buf)<=0:#a[i+1]+buf>0になるよう調整
        cur=mulsum[i+1]+buf
        buf=1-mulsum[i+1]
        cnt2=cnt2+(1-cur)
        #mp.append(1)
    else:
        i=i
        #mp.append(mulsum[i+1])
    i=i+2
    #print(buf,cnt2)
#print(mp,cnt2)
print(min(cnt,cnt2))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
S=[A[0]]
for i in range(n-1):
  S.append(S[-1]+A[i+1])
ans1=0
s1=0
a=-1
for i in range(n):
  a=a*(-1)
  if a==1:
    ans1=ans1+max(0,1-(S[i]+s1))
    s1=s1+max(0,1-(S[i]+s1))
  else:
    ans1=ans1+max(0,S[i]+s1+1)
    s1=s1-max(0,S[i]+s1+1)
ans2=0
a=1
s2=0
for i in range(n):
  a=a*(-1)
  if a==1:
    ans2=ans2+max(0,1-(S[i]+s2))
    s2=s2+max(0,1-(S[i]+s2))
  else:
    ans2=ans2+max(0,S[i]+s2+1)
    s2=s2-max(0,S[i]+s2+1)
print(min(ans1,ans2))

Submission status: Accepted

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

S1 = 0
S2 = 0
#S1が奇数番目が正の場合、S2が偶数番目が負の場合
cnt1 = 0
cnt2 = 0

for i,num in enumerate(a):
    S1 += num
    if i % 2 == 0 and S1 <= 0:
        cnt1 += 1 - S1
        S1 = 1
    if i % 2 != 0 and S1 >= 0:
        cnt1 += 1 + S1
        S1 = -1

    S2 += num
    if i % 2 == 0 and S2 >= 0:
        cnt2 += 1 + S2
        S2 = -1
    if i % 2 != 0 and S2 <= 0:
        cnt2 += 1 - S2
        S2 = 1

print(cnt1 if cnt1 <= cnt2 else cnt2)

Submission status: Accepted

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

X = [0]
for i in range(n):
    if i % 2 == 0:
        X.append(1)
    else:
        X.append(-1)

Y = [-x for x in X]

x = 0
AX = [0] + A
for i in range(1, n + 1):
    temporary = AX[i - 1] + AX[i]
    if temporary * X[i] > 0:
        AX[i] = temporary
    else:
        x += abs(temporary - X[i])
        AX[i] = X[i]

y = 0
AY = [0] + A
for i in range(1, n + 1):
    temporary = AY[i - 1] + AY[i]
    if temporary * Y[i] > 0:
        AY[i] = temporary
    else:
        y += abs(temporary - Y[i])
        AY[i] = Y[i]

print(min(x, y))

Submission status: Accepted

Solution code:
# solution
import math
import io

data=int(input())
qwe = (list(map(int,input().split())))
score1=score2=0
cnt1=cnt2=0
for i ,num in enumerate(qwe):
	score1+=num
	if score1<=0 and i%2==0:
		cnt1+=1-score1
		score1=1
	elif score1>=0 and i%2!=0:
		cnt1+=1+score1
		score1=-1
		
	score2+=num
	if score2<=0 and i%2!=0:
		cnt2+=1-score2
		score2=1
	elif score2>=0 and i%2==0:
		cnt2+=1+score2
		score2=-1
print(min(cnt1,cnt2))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

po = [a[i] for i in range(n)]

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

co = 0

ans = 0

for i in range(n):
    po[i] += co
    if i % 2 == 0:
        if po[i] > 0:
            continue
        else:
            co += abs(po[i]) + 1
            ans += abs(po[i]) + 1

    else:
        if po[i] < 0:
            continue
        else:
            co -= abs(po[i]) + 1
            ans += abs(po[i]) + 1
anss = 0
co = 0
po = [a[i] for i in range(n)]

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

for i in range(n):
    po[i] += co
    if i % 2 != 0:
        if po[i] > 0:
            continue
        else:
            co += abs(po[i]) + 1
            anss += abs(po[i]) + 1

    else:
        if po[i] < 0:
            continue
        else:
            co -= abs(po[i]) + 1
            anss += abs(po[i]) + 1
print(min(ans,anss))

Submission status: Accepted

Solution code:
def solve(n, arr):
  a = [x for x in arr]
  res = 0
  s = [0 for i in range(n)]
  if a[0] <= 0:
    res += a[0] * (-1) + 1
    a[0] += a[0] * (-1) + 1
  s[0] = a[0]
  for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    if s[i - 1] > 0 and s[i] >= 0:
      res += s[i - 1] + a[i] + 1
      a[i] -= s[i - 1] + a[i] + 1
    elif s[i - 1] < 0 and s[i] <= 0:
      res += 1 - s[i - 1] - a[i]
      a[i] += 1 - s[i - 1] - a[i]
    s[i] = s[i - 1] + a[i]
  return res

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

  print(min(solve(n, a), solve(n, list(map(lambda x: x * (-1), a)))))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = [a[0] for _ in range(n)]
t = [a[0] for _ in range(n)]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    t[i] = t[i - 1] + a[i]
x, y = 0, 0
ans1, ans2 = 0, 0
for i in range(n):
    ss = s[i] + x
    tt = t[i] + y
    if i % 2 == 0:
        if ss <= 0:
            x += abs(ss) + 1
            ans1 += abs(ss) + 1
        if tt >= 0:
            y -= abs(tt) + 1
            ans2 += abs(tt) + 1
    else:
        if ss >= 0:
            x -= abs(ss) + 1
            ans1 += abs(ss) + 1
        if tt <= 0:
            y += abs(tt) + 1
            ans2 += abs(tt) + 1
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
sum=0
cnt=0
# 奇数+
for i in range(n):
    sum+=a[i]
    if i%2==0:
        if sum>=0:
            cnt+=(sum+1)
            sum=-1
    else:
        if sum<=0:
            cnt+=(1-sum)
            sum=1
cnt_sbst=cnt
# 奇数-
cnt=0
sum=0
for i in range(n):
    sum+=a[i]
    if i%2==1:
        if sum>=0:
            cnt+=(sum+1)
            sum=-1
    else:
        if sum<=0:
            cnt+=(1-sum)
            sum=1
cnt_plus=cnt
ans=min(cnt_plus,cnt_sbst)
print(ans)

Submission status: Accepted

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

def check(sign):
    a_cnt=0
    a_sum=0
    for a in an:
        a_sum+=a
        if a_sum*sign<=0:
            a_cnt+=abs(a_sum-sign)
            a_sum=sign
        sign*=-1

        # print(a_sum, a_cnt)

    return a_cnt

print(min(check(1),check(-1)))

Submission status: Accepted

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

a0 = A[0]
if a0 > 0:
    S1, cnt1 = a0, 0
    S2, cnt2 = -1, abs(a0) + 1
elif a0 < 0:
    S1, cnt1 = 1, abs(a0) + 1
    S2, cnt2 = a0, 0
else:
    S1, cnt1 = 1, 1
    S2, cnt2 = -1, 1

S = S1
cnt = cnt1
for i in range(1, N):
    nS = S + A[i]
    if S > 0:
        if nS > 0:
            cnt += abs(nS) + 1
            nS = -1
    elif S < 0:
        if nS < 0:
            cnt += abs(nS) + 1
            nS = 1
    S = nS
ans = cnt

S = S2
cnt = cnt2
for i in range(1, N):
    nS = S + A[i]
    if S > 0:
        if nS >= 0:
            cnt += abs(nS) + 1
            nS = -1
    elif S < 0:
        if nS <= 0:
            cnt += abs(nS) + 1
            nS = 1
    S = nS
ans = min(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

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

def main():
    c1 = c2 = s1 = s2 = 0
    for i in range(n):
        s1 += a[i]
        s2 += a[i]
        if i & 1:
            if s1 >= 0:
                c1 += s1 + 1
                s1 = -1
            if s2 <= 0:
                c2 += 1 - s2
                s2 = 1
        else:
            if s1 <= 0:
                c1 += 1 - s1
                s1 = 1
            if s2 >= 0:
                c2 += s2 + 1
                s2 = -1
    print(min(c1, c2))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pytHon3
# -*- coding: utf-8 -*-


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

    s = [A[0]]

    for i in range(1, N):
        s.append(s[-1] + A[i])

    cnt_a = 0
    base = 0
    for i in range(N):
        if ((base + s[i] >= 0) and (i % 2 == 1)) \
                or ((base + s[i] <= 0) and (i % 2 == 0)):
            cnt_a += (1 + abs(base + s[i]))
            base += (1 + abs(base + s[i])) * (-1) ** i

    cnt_b = 0
    base = 0
    for i in range(N):
        if ((base + s[i] <= 0) and (i % 2 == 1)) \
                or ((base + s[i] >= 0) and (i % 2 == 0)):
            cnt_b += (1 + abs(base + s[i]))
            base -= (1 + abs(base + s[i])) * (-1) ** i

    print(min(cnt_a, cnt_b))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def cnt(p):
  s=d=0
  for i in range(n):
    c=(s+a[i])*p
    if c<=0:
      d+=(1-c)
      s=p
    else:
      s+=a[i]
    p*=(-1)
  return d

da=cnt(1)
db=cnt(-1)
print(min(da,db))

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
  n = int(input())
  A = readInts()
  
  cur = 0
  ans1 = 0
  for i in range(n):
    cur += A[i]
    if i % 2:
      if cur <= 0:
        ans1 += -cur+1
        cur = 1
    else:
      if cur >= 0:
        ans1 += cur + 1
        cur = -1
  cur = 0
  ans2 = 0
  for i in range(n):
    cur += A[i]
    if i % 2:
      if cur >= 0:
        ans2 += cur + 1
        cur = -1
    else:
      if cur <= 0:
        ans2 += -cur + 1
        cur = 1
  print(min(ans1,ans2))
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# coding: utf-8
n=int(input())
A=list(map(int,input().split()))

S1=0
cost1=0
for i in range(n):
    if i%2==0:
        if S1+A[i]>0:
            S1+=A[i]
        else:
            cost1+=abs(S1+A[i])+1
            S1=1
    else:
        if S1+A[i]<0:
            S1+=A[i]
        else:
            cost1+=abs(S1+A[i])+1
            S1=-1

S2=0
cost2=0
for i in range(n):
    if i%2==0:
        if S2+A[i]<0:
            S2+=A[i]
        else:
            cost2+=abs(S2+A[i])+1
            S2=-1
    else:
        if S2+A[i]>0:
            S2+=A[i]
        else:
            cost2+=abs(S2+A[i])+1
            S2=1
    
print(min(cost1,cost2))

Submission status: Accepted

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

res1 = 0
S = 0
# 偶数番目のとき正
for i in range(n):
    S += a[i]
    if i % 2 == 0:
        if S <= 0:
            res1 += abs(1 - S)
            S = 1
    else:
        if S >= 0:
            res1 += abs(-1 - S)
            S = -1

res2 = 0
S = 0
for i in range(n):
    S += a[i]
    if i % 2 == 1:
        if S <= 0:
            res2 += abs(1 - S)
            S = 1
    else:
        if S >= 0:
            res2 += abs(-1 - S)
            S = -1

print(min(res1, res2))

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

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

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

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

print(min(init_pos, init_neg))

Submission status: Accepted

Solution code:
n=int(input())

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

kp=0
asum=0
flag=-1
for i in range(n):
    asum=asum+a[i]
    if flag==-1:
        if asum>=0:
            kp=kp+asum+1
            asum=-1
    else:
        if asum<=0:
            kp=kp+1-asum
            asum=1
    flag=-flag
#    print(asum)
#print("-----",kp)            
km=0
asum=0
flag=1
for i in range(n):
    asum=asum+a[i]
    if flag==-1:
        if asum>=0:
            km=km+asum+1
            asum=-1
    else:
        if asum<=0:
            km=km+1-asum
            asum=1
    flag=-flag
#    print(asum)
#print("-----",km)            

print(min(kp,km))

Submission status: Accepted

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

x=0#pmpm
y=0
sum1=0
sum2=0

for i in range(n):
  sum1+=a[i]
  sum2+=b[i]
  if(i%2==0):
    if(sum1<=0):
      x+=1-sum1
      a[i]+=1-sum1
      sum1+=1-sum1
    if(sum2>=0):
      y+=sum2+1
      b[i]-=sum2+1
      sum2-=sum2+1
  else:
    if(sum1>=0):
      x+=sum1+1
      a[i]-=1+sum1
      sum1-=1+sum1
    if(sum2<=0):
      y+=1-sum2
      b[i]+=1-sum2
      sum2+=1-sum2
print(min(x,y))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
a=list(map(int,input().split()))
cnt1=0
now=0
for i in range(n):
    now+=a[i]
    if i%2==0:
        if now<=0:
            cnt1+=1-now
            now=1
    else:
        if now>=0:
            cnt1+=now+1
            now=-1
cnt2=0
now=0
for i in range(n):
    now+=a[i]
    if i%2==1:
        if now<=0:
            cnt2+=1-now
            now=1
    else:
        if now>=0:
            cnt2+=now+1
            now=-1

print(min(cnt1,cnt2))

Submission status: Accepted

Solution code:
import copy
n = int(input())
*A, = map(int, input().split())


def solve(p):
    r = 0
    t = 0
    for a in A:
        t += a
        if t * p <= 0:
            r += abs(p - t)
            t = p
        p *= -1
    return r


print(min(solve(1), solve(-1)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans1 = 0
num = 0
f1 = 1
for i in range(n):
    num += a[i]
    if f1:
        if num <=0:
            ans1 += 1-num
            num = 1
        f1 = 0
    else:
        if num >= 0:
            ans1 += num+1
            num = -1
        f1 = 1
ans2 = 0
num = 0
f1 = 0
for i in range(n):
    num += a[i]
    if f1:
        if num <=0:
            ans2 += 1-num
            num = 1
        f1 = 0
    else:
        if num >= 0:
            ans2 += num+1
            num = -1
        f1 = 1
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
def solve(A, p):
  act = 0
  total = 0
  for a in A:
    total += a
    if total * p < 1:
      act += abs(p - total)
      total = p
    p *= -1
  return act
ans = min(solve(A, 1), solve(A, -1))
print(ans)

Submission status: Accepted

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

temp = 0
cand1 = 0
for i in range(n):
    temp += s[i]
    if i%2 == 0:#正になってほしい
        if temp <= 0:
            cand1 += abs(temp-1)
            temp = 1
    else:#負になって欲しい
        if temp >= 0:
            cand1 += abs(temp+1)
            temp = -1

temp = 0
cand2 = 0
for i in range(n):
    temp += s[i]
    if i%2 == 0:
        if temp >= 0:
            cand2 += abs(temp+1)
            temp = -1
    else:
        if temp <= 0:
            cand2 += abs(temp-1)
            temp = 1

print(min(cand2,cand1))

Submission status: Accepted

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


def f(pm):
    ans, s = 0, 0
    for a in A:
        s += a
        if s * pm <= 0:
            d = abs(s - pm)
            ans += d
            s += d * pm
        pm *= -1
    return ans


print(min(f(1), f(-1)))

Submission status: Accepted

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

ans = float('inf')

cA = A[:]
cs = 0
cnt = 0
for i, a in enumerate(cA):
    if i%2 == 0: #ここまでの累積和が正
        if cs + a > 0:
            cs += a
        else:
            cA[i] += 1-(cs+a)
            cnt += 1-(cs+a)
            cs = 1
    else:
        if cs + a < 0:
            cs += a
        else:
            cA[i] += -1-(cs+a)
            cnt += abs(-1-(cs+a))
            cs = -1
ans = min(ans,cnt)

cA = A[:]
cs = 0
cnt = 0
for i, a in enumerate(cA):
    if i%2 == 1: #ここまでの累積和が正
        if cs + a > 0:
            cs += a
        else:
            cA[i] += 1-(cs+a)
            cnt += 1-(cs+a)
            cs = 1
    else:
        if cs + a < 0:
            cs += a
        else:
            cA[i] += -1-(cs+a)
            cnt += abs(-1-(cs+a))
            cs = -1
ans = min(ans,cnt)
print(ans)

Submission status: Accepted

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

def count(sign):
    
    count = 0
    a_sum = 0
    for a in a_list:
        a_sum +=a
        if a_sum*sign <= 0: 
            ope = sign - a_sum
            a_sum += ope
            count += abs(ope)
        sign *= -1
    return count
print(min(count(1),count(-1)))

Submission status: Accepted

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

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += (idx&(-idx))
    return


BIT = [0]*(n+1)
for i,e in enumerate(a):
   BIT_update(i+1,e)
ans1=0
for i in range(1,n+1):
    SUM=BIT_query(i)
    if i%2==1:
        if SUM<=0:
            ans1+=1-SUM
            BIT_update(i,1-SUM)
    else:
        if SUM>=0:
            ans1+=1+SUM
            BIT_update(i,-1-SUM)


BIT = [0]*(n+1)
for i,e in enumerate(a):
    BIT_update(i+1,e)
ans2=0
for i in range(1,n+1):
    SUM=BIT_query(i)
    if i%2==0:
        if SUM<=0:
            ans2+=1-SUM
            BIT_update(i,1-SUM)
    else:
        if SUM>=0:
            ans2+=1+SUM
            BIT_update(i,-1-SUM)

print(min(ans1,ans2))

Submission status: Accepted

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

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

ans=10**15
for t in [1,-1]:
    r=0
    cnt=0
    T=t
    for i in range(N):
        r+=A[i]
        if(T>0 and r<=0):
            cnt+=1-r
            r+=1-r
        if(T<0 and r>=0):
            cnt+=r+1
            r-=r+1
        T*=-1
    ans=min(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
t = 1
cand1 = 0
tmp = 0
for ai in a:
    if (tmp + ai) * t <= 0:
        cand1 += abs(tmp + ai - t)
        tmp = t
    else:
        tmp += ai
    t *= -1
t = -1
cand2 = 0
tmp = 0
for ai in a:
    if (tmp + ai) * t <= 0:
        cand2 += abs(tmp + ai - t)
        tmp = t
    else:
        tmp += ai
    t *= -1

print(min(cand1, cand2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
# + - + - 
su=0
op1=0
for i in range(n):
#    print(i,su,end=' i,su\n')
    if i%2==0:
        #su>0
        if su+a[i]<=0:
            diff=1-(su+a[i])
            op1+=diff
            su+=diff
 #           print(i,diff)
    if i%2==1:
        #su<0
        if su+a[i]>=0:
            diff=(su+a[i])+1
            op1+=diff
            su-=diff
  #          print(i,diff)
    su+=a[i]
su=0
op2=0
for i in range(n):
   # print(i,su,end=' i,su\n')
    if i%2==1:
        #su>0
        if su+a[i]<=0:
            diff=1-(su+a[i])
            op2+=diff
            su+=diff
    #        print(i,diff)
    if i%2==0:
        #su<0
        if su+a[i]>=0:
            diff=(su+a[i])+1
            op2+=diff
            su-=diff
     #       print(i,diff)
    su+=a[i]
print(min(op1,op2))

Submission status: Accepted

Solution code:
import sys,copy
from itertools import accumulate

input=sys.stdin.readline

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

A=list(accumulate(A))
B=copy.copy(A)
test1=0
s=0
for i in range(0,N):
    A[i]+=s
    if i%2==0:
        if 0>=A[i]:
            test1+=1-A[i]
            s+=1-A[i]
    else:
        if A[i]>=0:
            test1+=A[i]+1
            s-=A[i]+1


test2=0
s=0
for i in range(0,N):
    B[i]+=s
    if i%2==0:
        if B[i]>=0:
            test2+=B[i]+1
            s-=B[i]+1
    else:
        if 0>=B[i]:
            test2+=1-B[i]
            s+=1-B[i]

print(min(test1,test2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
sum = 0
res = [0,0]
for change in range(2):
  sum = 0
  for i in range(n):
    if i % 2 == change:
      if sum + a[i] < 0: # -だったら
        #temp = -1 - sum - a[i]
        temp = 1 - sum - a[i]
        res[change] += temp
        sum += temp
      elif sum + a[i] == 0:
        sum += 1
        res[change] += 1
    else:
      if sum + a[i] > 0:
        #temp = 1 - sum - a[i]
        temp = -1 - sum - a[i]
        res[change] -= temp
        sum += temp
      elif sum + a[i] == 0:
        sum -= 1
        res[change] += 1
    sum += a[i]
print(min(res[0],res[1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
S = [0]*N
S[0] = a[0]

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

count = [0]*N
num = [0]*2
for i in range(2):
    value = 0
    for j in range(N):
        if (S[j]+value)*((-1)**(i+j)) <= 0:
            num[i] += abs(S[j] + value - (-1)**(i+j))
            value += (-1)**(i+j) - (S[j]+value)
        #print(i,num,value)

#print(S)
print(min(num))

Submission status: Accepted

Solution code:
_,*l=map(int,open(0).read().split())
def f(s):
  c=t=0
  for i in l:
    t+=i
    if s*t<=0: c+=abs(t-s); t=s
    s*=-1
  return c
print(min(f(1),f(-1)))

Submission status: Accepted

Solution code:
input()
l=list(map(int,input().split()))
def f(s):
  c=t=0
  for i in l:
    t+=i
    if s*t<=0: c+=abs(t-s); t=s
    s*=-1
  return c
print(min(f(1),f(-1)))

Submission status: Accepted

Solution code:
input()
l=list(map(int,input().split()))
def f(b):
  c=s=0
  for i in l:
    if b:
      if s+i>0: s+=i
      else: c-=s+i-1; s=1
    else:
      if s+i<0: s+=i
      else: c+=s+i+1; s=-1
    b=1-b
  return c
print(min(f(0),f(1)))

Submission status: Accepted

Solution code:
import sys

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

min_a = 0
sum_a = 0
for i in range(n):
    sum_a += a[i]
    if i % 2 == 0:
        if sum_a <= 0:
            min_a += abs(sum_a) + 1
            sum_a += abs(sum_a) + 1
    else:
        if sum_a >= 0:
            min_a += abs(sum_a) + 1
            sum_a -= abs(sum_a) + 1

min_b = 0
sum_b = 0
for i in range(n):
    sum_b += a[i]
    if i % 2 == 0:
        if sum_b >= 0:
            min_b += abs(sum_b) + 1
            sum_b -= abs(sum_b) + 1
    else:
        if sum_b <= 0:
            min_b += abs(sum_b) + 1
            sum_b += abs(sum_b) + 1

print(min(min_a, min_b))

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    odd, even = 0, 0
    cnt1 = 0
    for i in range(n):
        if i % 2 == 0:
            odd += a[i]
            if odd + even <= 0:
                tmp = 1 - (odd + even)
                odd += tmp
                cnt1 += tmp
        else:
            even += a[i]
            if 0 <= odd + even:
                tmp = -1 - (odd + even)
                even += tmp
                cnt1 += abs(tmp)
    
    odd, even = 0, 0
    cnt2 = 0
    for i in range(n):
        if i % 2 == 0:
            odd += a[i]
            if 0 <= odd + even:
                tmp = -1 - (odd + even)
                odd += tmp
                cnt2 += abs(tmp)
        else:
            even += a[i]
            if odd + even <= 0:
                tmp = 1 - (odd + even)
                even += tmp
                cnt2 += tmp
    
    ans = min(cnt1, cnt2)
    print(ans)


if __name__ == '__main__':
    solve()