Submission #62808958

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n=int(input())
s=input()
list_1 = []
ct = 0
l0 = [-1, -1]
while True:
    if ct == n:
        break
    if s[ct] == "1":
        if l0[0] == -1:
            l0[0] = ct
        while True:
            if ct == n:
                break
            if s[ct] == "0":
                l0[1] = ct - 1
                list_1.append(l0)
                l0 = [-1, -1]
                break
            if s[ct] == "1" and ct == n-1:
                l0[1] = ct
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

n=int(input())
s=input()
list_1 = []
ct = 0
l0 = [-1, -1]
while True:
    if ct == n:
        break
    if s[ct] == "1":
        if l0[0] == -1:
            l0[0] = ct
        while True:
            if ct == n:
                break
            if s[ct] == "0":
                l0[1] = ct - 1
                list_1.append(l0)
                l0 = [-1, -1]
                break
            if s[ct] == "1" and ct == n-1:
                l0[1] = ct
                list_1.append(l0)
                l0 = [-1, -1]
                break
            ct += 1
    ct += 1
ans = 0
left_list = []
right_list = []

if len(list_1) != 1:
    num = list_1[0][1] - list_1[0][0] + 1
    for i in range(1, len(list_1)):
        left_list.append((list_1[i][0] - list_1[i - 1][1] - 1) * num)
        num += list_1[i][1] - list_1[i][0] + 1
    num2 = list_1[-1][1] - list_1[-1][0] + 1
    for j in range(len(list_1) - 2, -1,-1):
        right_list.append((list_1[j + 1][0] - list_1[j][1] - 1) * num2)
        num2 += list_1[j][1] - list_1[j][0] + 1
    accuml = [0]
    accumr = [0]
    for i in range(len(right_list)):
        accuml.append(accuml[-1] + left_list[i])
        accumr.append(accumr[-1] + right_list[i])
    # print(left_list)
    # print(right_list)
    # print(accuml)
    # print(accumr)
    ans = accuml[-1]
    for i in range(len(accuml)):
        ans = min(ans, accumr[i] + accuml[-1-i])
print(ans)

Submission Info

Judge Result