Advertisement
mfgnik

Untitled

Mar 18th, 2023
444
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.76 KB | None | 0 0
  1. n = int(input())
  2. numbers = list(map(int, input().split()))
  3.  
  4. pref_sums = [0]
  5. pref_sums_indexes = {0: 0}
  6.  
  7. interesting_left_to_right = {}
  8.  
  9. for index, number in enumerate(numbers):
  10.     pref_sums.append(pref_sums[-1] + number)
  11.     if pref_sums[-1] in pref_sums_indexes:
  12.         left_index = pref_sums_indexes[pref_sums[-1]]
  13.         interesting_left_to_right[left_index] = index
  14.     pref_sums_indexes[pref_sums[-1]] = index + 1
  15.  
  16.  
  17. good_amount = 0
  18. current_good_left = 0
  19. for left in range(n):
  20.     while current_good_left < n and (current_good_left < left or current_good_left not in interesting_left_to_right):
  21.         current_good_left += 1
  22.     if current_good_left < n:
  23.         good_amount += n - interesting_left_to_right[current_good_left]
  24.  
  25. print(good_amount)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement