a_chn

Untitled

Jan 22nd, 2025
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.91 KB | None | 0 0
  1. import sys
  2.  
  3. def main():
  4.     patch_count, enemy_count, allies = map(int, sys.stdin.readline().split())
  5.     patches = [tuple(map(int, sys.stdin.readline().split())) for _ in range(patch_count)]
  6.     enemies = [-5_000_000_000] + [int(sys.stdin.readline()) for _ in range(enemy_count)] + [5_000_000_000]
  7.  
  8.     patches.sort()
  9.     enemies.sort()
  10.  
  11.     possibilities = []
  12.  
  13.     left, right = 0, 0
  14.  
  15.     for start, end in zip(enemies[:-1], enemies[1:]):
  16.         left, right = max(left, right), max(left, right)
  17.  
  18.         while left < patch_count and patches[left][0] < start:
  19.             left += 1
  20.             right += 1
  21.  
  22.         if left >= patch_count or patches[left][0] >= end:
  23.             continue
  24.  
  25.         maximum = current = patches[left][1]
  26.         total = 0
  27.        
  28.         i = left
  29.         while i < patch_count and patches[i][0] < end:
  30.             total += patches[i][1]
  31.             i += 1
  32.  
  33.         while left <= right < patch_count - 1 and patches[right + 1][0] < end:
  34.             while left <= right < patch_count - 1 and patches[right + 1][0] < end:
  35.                 right += 1
  36.  
  37.                 dist = patches[left][0] - start
  38.                 cow_loc = patches[left][0] + dist - 1
  39.                 right_dist = end - patches[right][0]
  40.                 dist_to_right = patches[right][0] - cow_loc
  41.                 if dist_to_right > right_dist:
  42.                     right -= 1
  43.                     break
  44.  
  45.                 current += patches[right][1]
  46.  
  47.             maximum = max(maximum, current)
  48.             current -= patches[left][1]
  49.             left += 1
  50.  
  51.         possibilities.append(maximum)
  52.         possibilities.append(total - maximum)
  53.  
  54.     possibilities.sort(reverse=True)
  55.     print(sum(possibilities[:min(allies, len(possibilities))]))
  56.  
  57. if __name__ == "__main__":
  58.     # Redirect input and output
  59.     # sys.stdin = open("test.in", "r")
  60.     # sys.stdout = open("test.out", "w")
  61.    
  62.     main()
  63.  
Advertisement
Add Comment
Please, Sign In to add comment