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()))
ans = float('inf')
# 各Aiを見ていく時 iが奇数、偶数どちらの時の和を負の数にするか
for case in range(2):
    count = 0  # 操作回数
    sum_a = 0  # Ai までの数の和
    up = case  # 和を正整数にするか
    for a in A:
        sum_a += a
        diff = 0  # a をどの程度操作するか。
        if up:  # 正整数であるべき
            if sum_a < 1:  # 1未満の数(0か負数)
                diff = 1 - sum_a
        else:  # 負整数であるべき
            if -1 < sum_a:  # -1より大きい数(0か正整数)
                diff = -1 - sum_a
        sum_a += diff  # Ai までの和に操作後の値を適用する
        count += abs(diff)  # 操作回数を加算する
        up ^= 1  # 次回は今回とは逆の符号にする
    ans = min(count, ans)  # 最小操作回数を更新
print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def calc_cost_pos_neg(seq):
        n = len(seq)
        cnt = 0
        total = 0
        for i in range(n):
            if i % 2 == 0 and seq[i] + total <= 0:
                cnt += (1 - (seq[i] + total))
                total += (1 - (seq[i] + total))
            elif i % 2 == 1 and seq[i] + total >= 0:
                cnt += ((seq[i] + total) - (-1))
                total -= ((seq[i] + total) - (-1))
        return cnt
    
    
    def calc_cost_neg_pos(seq):
        n = len(seq)
        cnt = 0
        total = 0
        for i in range(n):
            if i % 2 == 1 and seq[i] + total <= 0:
                cnt += (1 - (seq[i] + total))
                total += (1 - (seq[i] + total))
            elif i % 2 == 0 and seq[i] + total >= 0:
                cnt += ((seq[i] + total) - (-1))
                total -= ((seq[i] + total) - (-1))
        return cnt    

    
    n = ii()
    L = lmi()
    accum = list(accumulate(L))
    print(min(calc_cost_pos_neg(accum), calc_cost_neg_pos(accum)))
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())    
a = list(map(int, input().split()))
ans1 = 0
ans2 = 0
total1 = 0
total2 = 0
for i in range(n):
    total1 += a[i]
    if i % 2 == 0:
        if total1 <= 0:
            ans1 += abs(total1 - 1)
            total1 = 1
    else:
        if total1 >= 0:
            ans1 += abs(total1 + 1)
            total1 = -1
for i in range(n):
    total2 += a[i]
    if i % 2 == 0:
        if total2 >= 0:
            ans2 += abs(total2 + 1)
            total2 = -1
    else:
        if total2 <= 0:
            ans2 += abs(total2 - 1)
            total2 = 1
print(min(ans1, ans2))

Submission status: Accepted

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

ans1 = 0
total1 = 0
sign1 = True
for i in a:
    total1 += i
    if sign1 and total1 < 0:
        ans1 += abs(total1) + 1
        total1 = 1
    elif not sign1 and total1 > 0:
        ans1 += abs(total1) + 1
        total1 = -1
    elif sign1 and total1 == 0:
        ans1 += 1
        total1 = 1
    elif not sign1 and total1 == 0:
        ans1 += 1
        total1 = -1
    else:
        pass

    sign1 = not sign1

ans2 = 0
total2 = 0
sign2 = False
for j in a:
    total2 += j
    if sign2 and total2 < 0:
        ans2 += abs(total2) + 1
        total2 = 1
    elif not sign2 and total2 > 0:
        ans2 += abs(total2) + 1
        total2 = -1
    elif sign2 and total2 == 0:
        ans2 += 1
        total2 = 1
    elif not sign2 and total2 == 0:
        ans2 += 1
        total2 = -1
    else:
        pass

    sign2 = not sign2

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))

S = [0 for _ in range(n)]
acum = 0
for i in range(n):
    acum += A[i]
    S[i] = acum
# print(S)

costs = [0, 0]
for p in (0, 1):
    S_tmp = S[:]
    cost = 0 # BA`:n2s?t
    diff = 0 # +-B$NA`:n$G$NJQF0
    for i in range(n):
        # nB$H0lCW$9$kJ}$rIi$K$9$k
        # print(p, diff + S_tmp[i])
        if i % 2 == p:
            if diff + S_tmp[i] >= 0:
                tmp_cost = diff + S_tmp[i] + 1
                diff -= tmp_cost
                cost += tmp_cost
                # print("cost", cost)
        else:
            # B@5$KJQ49$9$k%3%9%H
            if diff + S_tmp[i] <= 0:
                tmp_cost = 1 - diff - S_tmp[i]
                diff += tmp_cost # +1B$KJQ49$9$k
                cost += tmp_cost
                # print("cost", cost)
    costs[p] = cost

# print(costs)
print(min(costs))

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    n = int(stdin.readline())
    ar = map(int, stdin.readline().split())

    f = 0
    s = 0

    cf = 0
    cs = 0

    for idx, val in enumerate(ar):
        cf += val
        cs += val
        if idx % 2 == 0:
            if cf <= 0:
                f += 1 - cf
                cf = 1
            if cs >= 0:
                s += 1 + cs
                cs = -1
        else:
            if cs <= 0:
                s += 1 - cs
                cs = 1
            if cf >= 0:
                f += 1 + cf
                cf = -1
    print(min(s, f))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
a = list(accumulate([int(i) for i in input().split()]))
d = 0
ans = 0
for i, n in enumerate(a):
    n += d
    if i & 1:
        if n >= 0:
            ans += n + 1
            d -= n + 1
    # 奇数回目でマイナスのとき
    elif n <= 0:
        ans += - n + 1
        d += - n + 1
c = ans
ans = 0
d = 0
for i, n in enumerate(a):
    n += d
    if i & 1 == 0:
        if n >= 0:
            ans += n + 1
            d -= n + 1
    elif n <= 0:
        ans += - n + 1
        d += - n + 1
print(min(ans, c))

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

p = A[0] if A[0] > 0 else 1
pc = 0 if A[0] > 0 else 1 - A[0]
m = A[0] if A[0] < 0 else -1
mc = 0 if A[0] < 0 else 1 + abs(A[0])

for i in range(1, N):
    p += A[i]
    m += A[i]
    if i % 2 == 0:
        if p <= 0:
            pc += 1 - p
            p = 1
        if m >= 0:
            mc += 1 + m
            m = -1
    else:
        if p >= 0:
            pc += 1 + p
            p = -1
        if m <= 0:
            mc += 1 - m
            m = 1

print(min(pc, mc))

Submission status: Accepted

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

point = 0
point2 = 0

now = 0
now2 = 0

for i,j in enumerate(a):
    now += j
    now2 += j
    if i%2 == 0:
        if now <= 0:
            point += 1-now
            now = 1
        if now2 >= 0:
            point2 += 1+now2
            now2 = -1
    else:
        if now2 <= 0:
            point2 += 1-now2
            now2 = 1
        if now >= 0:
            point += 1+now
            now = -1

print(min(point,point2))

Submission status: Accepted

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

def check(mode):
    ans,s = 0,0
    if mode:##奇数番目が正
        for i in range(n):
            s += a[i]
            if i%2 == 0:
                if s <= 0:
                    ans += abs(s)+1
                    s = 1
            else:
                if s >= 0:
                    ans += abs(s)+1
                    s = -1
    else:
        for i in range(n):
            s += a[i]
            if i%2 == 0:
                if s >= 0:
                    ans += abs(s)+1
                    s = -1
            else:
                if s <= 0:
                    ans += abs(s)+1
                    s = 1
    return ans

print(min(check(True),check(False)))

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 == 1:
        if s <= 0:
            c1 += 1 - s
            s = 1

    else: 
        if s >= 0:
            c1 += 1 + s
            s = -1

c2 = 0
t = 0

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

print(min(c1, c2))

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 == 1:
        if s <= 0:
            c1 += 1 - s
            s = 1

    else:  # iが偶数
        if s >= 0:
            c1 += 1 + s
            s = -1

c2 = 0
s = 0

# 累積和の偶数番目を正とするパターン
for i in range(n):
    s += a[i]
    if i % 2 == 1:
        if s >= 0:
            c2 += 1 + s
            s = -1
    else:
        if s <= 0:
            c2 += 1 - s
            s = 1

print(min(c1, c2))

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def func(a, judge):
    sum_list = list(accumulate(a))
    x = 0
    num = 0

    length = len(sum_list)

    for i in range(length):
        if judge and sum_list[i] + x <= 0:
            num += 1 - (sum_list[i] + x)
            x += 1 - (sum_list[i] + x)

        if (not judge) and sum_list[i] + x >= 0:
            num += 1 + (sum_list[i] + x)
            x -= 1 + (sum_list[i] + x)

        judge = not judge

    return num


ans = min([func(A, True), func(A, False)])

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

#偶数項を正とする
    sumeven = 0
    cnteven = 0
    for i in range(n):
        sumeven += A[i]
        if i % 2 == 0:
            if sumeven <= 0:
                cnteven += abs(sumeven) + 1
                sumeven += abs(sumeven) + 1
        else:
            if sumeven >= 0:
                cnteven += (sumeven + 1)
                sumeven -= (sumeven + 1)

# 奇数項を正とする
    sumodd = 0
    cntodd = 0
    for i in range(n):
        sumodd += A[i]
        if i % 2 == 1:
            if sumodd <= 0:
                cntodd += abs(sumodd) + 1
                sumodd += abs(sumodd) + 1
        else:
            if sumodd >= 0:
                cntodd += (sumodd + 1)
                sumodd -= (sumodd + 1)

    print(min(cnteven, cntodd))
#    print(cnteven, cntodd)

resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    n=int(input())
    a=list(map(int,input().split()))
    ans=INF
    for f in range(2):
        s=0
        tmp=0
        for x in a:
            s+=x
            if f and s<=0:
                tmp+=1-s
                s=1
            elif not f and s>=0:
                tmp+=s+1
                s=-1
            f=not f
        ans=min(ans,tmp)
    print(ans)
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def n_op(a, p):
    s = accumulate(a)
    x = 0
    n = 0

    for si in s:
        if p and si + x <= 0:
            n += 1 - (si + x)
            x += 1 - (si + x)
        if (not p) and si + x >= 0:
            n += 1 + (si + x)
            x -= 1 + (si + x)
        p = not p

    return n


answer = min([n_op(a, True), n_op(a, False)])
print(answer)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    n = NI()
    a = LI()
    ans = INF
    for s in (1,-1):
        acc = 0
        cnt = 0
        x = s
        for i in range(n):
            acc += a[i]
            if acc * x <= 0:
                cnt += abs(x-acc)
                acc = x
            x = -x
        ans = min(ans,cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    n = NI()
    bit = [0] * (n+1)

    def add(i,x):
        while i <= n:
            bit[i] += x
            i += i & -i

    def query(i):
        x = 0
        while i > 0:
            x += bit[i]
            i -= i & -i
        return x

    for i,a in enumerate(LI()):
        add(i+1,int(a))

    ans = INF

    b = [bit,copy.copy(bit)]
    for s in (1,-1):
        bit = b[(s+1)//2]
        cnt = 0
        x = s
        for i in range(1,n+1):
            z = query(i)
            if z * x <= 0:
                add(i,x-z)
                cnt += abs(x-z)
            x = -x
        ans = min(ans,cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    n = NI()
    bit = [0] * (n+1)
    A = LI()
    def add(i,x):
        while i <= n:
            bit[i] += x
            i += i & -i

    def query(i):
        x = 0
        while i > 0:
            x += bit[i]
            i -= i & -i
        return x

    for i,a in enumerate(A):
        add(i+1,int(a))

    ans = INF
    bit_c = copy.deepcopy(bit)
    for s in (1,-1):
        bit = copy.deepcopy(bit_c)
        cnt = 0
        x = s
        for i in range(1,n+1):
            z = query(i)
            if z * x <= 0:
                add(i,x-z)
                cnt += abs(x-z)
            x = -x
        ans = min(ans,cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(min(c1, c2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
count_1 = 0
count_2 = 0
sum_1 = 0
sum_2 = 0

for i in range(len(a)):
    sum_1 += a[i]
    if i % 2 == 1:
        if sum_1 <= 0:
            count_1 += 1 - sum_1
            sum_1 = 1
    elif i % 2 == 0:
        if sum_1 >= 0:
            count_1 += sum_1 + 1
            sum_1 = -1

for i in range(len(a)):
    sum_2 += a[i]
    if i % 2 == 1:
        if sum_2 >= 0:
            count_2 += sum_2 + 1
            sum_2 = -1
    elif i % 2 == 0:
        if sum_2 <= 0:
            count_2 += 1 - sum_2
            sum_2 = 1

print(count_1 if count_1 < count_2 else count_2)

Submission status: Accepted

Solution code:
n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))

Submission status: Accepted

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

o=0
e=0

if res_o[0]<=0:
    o+=1-res_o[0]
    res_o[0]=1
if res_e[0]>=0:
    e+=res_e[0]+1
    res_e[0]=-1

for i in range(1,n):
    res_o[i]=res_o[i-1]+a[i]
    res_e[i]=res_e[i-1]+a[i]
    if i%2==0 and res_o[i]<=0:
        o+=(1-res_o[i])
        res_o[i]=1
    elif i%2==1 and res_o[i]>=0:
        o+=(res_o[i]+1)
        res_o[i]=-1
    if i%2==0 and res_e[i]>=0:
        e+=(1+res_e[i])
        res_e[i]=-1
    elif i%2==1 and res_e[i]<=0:
        e+=(1-res_e[i])
        res_e[i]=1
print(min(e,o))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
minnum = float('inf')
for m in range(2):
    ans = 0
    s = [0]*(n+1)
    tmp = a[0] 
    if m == 0:
        if a[0] >= 0:
            ans += a[0]+1
            a[0] = -1 
    else:
        if a[0] <= 0:
            ans += abs(a[0])+1
            a[0] = 1

    for i in range(n):
        s[i+1] = s[i] + a[i]
        if s[i] < 0:
            if s[i+1] != 0 and s[i+1] > 0:
                continue
            else:
                ans += abs(s[i+1])+1
                s[i+1] = 1
        elif s[i] > 0:
            if s[i+1] != 0 and s[i+1] < 0:
                continue
            else:
                ans += abs(s[i+1])+1   
                s[i+1] = -1

    minnum = min(minnum,ans)
    a[0] = tmp

print(minnum)

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate

    N = int(input())
    *A, = map(int, input().split())
    *acc, = accumulate(A)

    def count(w: int = 1) -> int:
        # m: -+-+-
        # w: +-+-+
        ret = 0
        add_val = 0
        for i, x in enumerate(acc):
            if (i & 1) ^ w:
                b = max(0, 1 - (x + add_val))
                ret += b
                add_val += b

            else:
                b = max(0, (x + add_val) - (-1))
                ret += b
                add_val -= b
        return ret

    ans = min(
        count(w=0),
        count(w=1)
    )

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def check(n,s,x):
    cnt=0
    f=0
    for i in range(n):
        if i%2==0:
            if (s[i]+f)*x<=0:
                cnt+=abs(x-s[i]-f)
                f+=x-s[i]-f
        else:
            if (s[i]+f)*x>=0:
                cnt+=abs(-x-s[i]-f)
                f+=-x-s[i]-f
    return cnt

def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))

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

    cnt1=check(n,s,1)
    cnt2=check(n,s,-1)
    print(min(cnt1,cnt2))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
n = ii()
A = iil()

cum = 0
ope = 0
# first plus case
for i,item in enumerate(A):
    cum += item
    if i%2 == 0 and cum <= 0:
        ope += abs(cum)+1
        cum = 1
    elif i%2 == 1 and cum >= 0:
        ope += cum+1
        cum = -1
#    print(cum)
tmp = ope

cum = 0
ope = 0
# first minus case
for i,item in enumerate(A):
    cum += item
    if i%2 == 1 and cum <= 0:
        ope += abs(cum)+1
        cum = 1
    elif i%2 == 0 and cum >= 0:
        ope += cum+1
        cum = -1
#print(tmp,ope)
print(min(tmp,ope))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    cnt_odd_plus, cnt_odd_minus = 0, 0
    R_plus, R_minus = [0], [0]
    for i in range(n):
        if i % 2 == 0:
            # 奇数番目までの和をプラスにしたいのに、0以下になってしまう場合は和が1になるように操作する
            if R_plus[-1] + A[i] <= 0:
                cnt_odd_plus += 1 - (R_plus[-1] + A[i])
                R_plus.append(1)
            else:
                R_plus.append(R_plus[-1] + A[i])

            # 奇数番目までの和をマイナスにしたいのに、0以上になってしまう場合は和が1になるように操作する
            if R_minus[-1] + A[i] >= 0:
                cnt_odd_minus += 1 + (R_minus[-1] + A[i])
                R_minus.append(-1)
            else:
                R_minus.append(R_minus[-1] + A[i])
        else:
            # 偶数番目までの和をマイナスにしたいのに、0以上になってしまう場合は和が-1になるように操作する
            if R_plus[-1] + A[i] >= 0:
                cnt_odd_plus += 1 + (R_plus[-1] + A[i])
                R_plus.append(-1)
            else:
                R_plus.append(R_plus[-1] + A[i])

            # 偶数番目までの和をプラスにしたいのに、0以下になってしまう場合は和が1になるように操作する
            if R_minus[-1] + A[i] <= 0:
                cnt_odd_minus += 1 - (R_minus[-1] + A[i])
                R_minus.append(1)
            else:
                R_minus.append(R_minus[-1] + A[i])

    res = min(cnt_odd_plus, cnt_odd_minus)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))

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

    cnt1=0
    s1=s[:]
    f1=0
    #1,-1,...
    for i in range(n):
        if i%2==0:
            if s1[i]+f1<=0:
                cnt1+=abs(1-s1[i]-f1)
                f1+=1-s1[i]-f1
        else:
            if s1[i]+f1>=0:
                cnt1+=abs(-1-s1[i]-f1)
                f1+=-1-s1[i]-f1
    
    cnt2=0
    s2=s[:]
    f2=0
    #-1,1,...
    for i in range(n):
        if i%2==0:
            if s2[i]+f2>=0:
                cnt2+=abs(-1-s2[i]-f2)
                f2+=-1-s2[i]-f2
        else:
            if s2[i]+f2<=0:
                cnt2+=abs(1-s2[i]-f2)
                f2+=1-s2[i]-f2
    print(min(cnt1,cnt2))

if __name__=="__main__":
    main()

Submission status: Accepted

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

def sol(S):
    ret = 0
    for a in A[1:]:
        b = a
        if S * (S + b) > 0:
            b = (abs(S) + 1) * (1 if S < 0 else -1)
        if S + b == 0:
            b = b - 1 if S > 0 else b + 1
        ret += abs(b - a)
        S += b
    return ret

if A[0] == 0:
    ans = min(sol(1), sol(-1)) + 1
else:
    ans = min(sol(A[0]), sol(-A[0] // abs(A[0])) + abs(A[0]) + 1)
print(ans)

Submission status: Accepted

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

def sol(S):
    ret = 0
    for a in A[1:]:
        b = a
        if S * (S + b) > 0:
            b = (abs(S) + 1) * (1 if S < 0 else -1)
        if S + b == 0:
            b = b - 1 if S > 0 else b + 1
        ret += abs(b - a)
        S += b
    return ret

if A[0] == 0:
    ans = min(sol(1), sol(-1)) + 1
else:
    ans = min(sol(A[0]), sol(-1 if A[0] > 0 else 1) + abs(A[0]) + 1)
print(ans)