AcWing 4656. 技能升级
原题链接
困难
作者:
SeiunSky
,
2023-01-09 20:08:17
,
所有人可见
,
阅读 127
py3 代码
import math
[l, mid, now, cnt, ans] = [0] * 5
r = 10**6
a = [0 for i in range(r + 10)]
b = [0 for i in range(r + 10)]
def sumd (r, n, t):
l = r - t * (n - 1)
return (l + r) * n >> 1
def check (x):
res = 0
for i in range(1, n + 1):
if a[i] > x:
res += math.ceil((a[i] - x) / b[i])
return res <= m
[n, m] = list(map(int, input().split()))
for i in range(1, n + 1):
[a[i], b[i]] = list(map(int, input().split()))
while l < r:
mid = l + r >> 1
if check (mid):
r = mid
else:
l = mid + 1
for i in range(1, n + 1):
if a[i] > l:
now = math.ceil((a[i] - l) / b[i])
cnt += now
ans += sumd (a[i], now, b[i])
print(ans + l * (m - cnt))