Advertisement
Zuneve

Untitled

Apr 29th, 2024
17
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. import sys
  2. from random import *
  3. from itertools import permutations
  4. from math import gcd
  5. input = lambda: sys.stdin.readline().strip()
  6.  
  7.  
  8. def mas():
  9. return list(map(int, input().split()))
  10. f = open("27_B_5142 (1).txt")
  11. n, m = map(int, f.readline().split())
  12. a = []
  13. for i in range(n):
  14. x, y = map(int, f.readline().split())
  15. z = (y + 49) // 50
  16. a.append([x, y, z])
  17. a.sort()
  18. pref_y = [0] * (n + 1)
  19. pref_z = [0] * (n + 1)
  20. for i in range(1, n + 1):
  21. pref_y[i] = pref_y[i - 1] + a[i - 1][1]
  22. pref_z[i] = pref_z[i - 1] + a[i - 1][2]
  23.  
  24.  
  25. ans = -1
  26. z = -1
  27. for i in range(n):
  28. l = -1
  29. r = i
  30. while r - l > 1:
  31. mid = (l + r) >> 1
  32. if a[i][0] - a[mid][0] <= m:
  33. r = mid
  34. else:
  35. l = mid
  36. ind1 = r
  37. l = i
  38. r = n
  39. while r - l > 1:
  40. mid = (l + r) >> 1
  41. if a[mid][0] - a[i][0] <= m:
  42. l = mid
  43. else:
  44. r = mid
  45. ind2 = l
  46. if pref_y[ind2 + 1] - pref_y[ind1] > ans:
  47. ans = pref_y[ind2 + 1] - pref_y[ind1]
  48. z = pref_z[ind2 + 1] - pref_z[ind1]
  49. elif pref_y[ind2 + 1] - pref_y[ind1] == ans and pref_z[ind2 + 1] - pref_z[ind1] < z:
  50. z = pref_z[ind2 + 1] - pref_z[ind1]
  51.  
  52. print(z)
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement