Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- def main():
- patch_count, enemy_count, allies = map(int, sys.stdin.readline().split())
- patches = [tuple(map(int, sys.stdin.readline().split())) for _ in range(patch_count)]
- enemies = [-5_000_000_000] + [int(sys.stdin.readline()) for _ in range(enemy_count)] + [5_000_000_000]
- patches.sort()
- enemies.sort()
- possibilities = []
- left, right = 0, 0
- for start, end in zip(enemies[:-1], enemies[1:]):
- left, right = max(left, right), max(left, right)
- while left < patch_count and patches[left][0] < start:
- left += 1
- right += 1
- if left >= patch_count or patches[left][0] >= end:
- continue
- maximum = current = patches[left][1]
- total = 0
- i = left
- while i < patch_count and patches[i][0] < end:
- total += patches[i][1]
- i += 1
- while left <= right < patch_count - 1 and patches[right + 1][0] < end:
- while left <= right < patch_count - 1 and patches[right + 1][0] < end:
- right += 1
- dist = patches[left][0] - start
- cow_loc = patches[left][0] + dist - 1
- right_dist = end - patches[right][0]
- dist_to_right = patches[right][0] - cow_loc
- if dist_to_right > right_dist:
- right -= 1
- break
- current += patches[right][1]
- maximum = max(maximum, current)
- current -= patches[left][1]
- left += 1
- possibilities.append(maximum)
- possibilities.append(total - maximum)
- possibilities.sort(reverse=True)
- print(sum(possibilities[:min(allies, len(possibilities))]))
- if __name__ == "__main__":
- # Redirect input and output
- # sys.stdin = open("test.in", "r")
- # sys.stdout = open("test.out", "w")
- main()
Advertisement
Add Comment
Please, Sign In to add comment