Submission #550325

#	Time	Username	Problem	Language	Result	Execution time	Memory
550325		sealnot123	City (BOI06_city)	Cpython 3	90 / 100	1093 ms	3828 KiB

city

import io

(n,t,k) = input().split()
n = int(n)
t = int(t)
k = int(k)
c = []
for i in range(3,3+k):
    c.append(int(input()))
#print(n,t,k)
l = int(c[0])
r = int(20*1e38)
while l < r:
    m = (l+r)//2
    s = 0
    for i in range(0, k):
        if m < c[i]:
            break
        dist = (m-c[i])//t + 1
        s += 2*dist*(dist+1)
    if s >= n :
        r = m
    else :
        l = m+1
# buy everything that is "less" than
cum = 0
ans = 0
for i in range(0, k):
    if l-1 < c[i]:
        break
    dist = (l-1-c[i])//t + 1
    cum += 2*dist*(dist+1)
    ans += 2*(c[i]-t)*dist*(dist+1)
    ans += t*dist*(dist+1)*(2*dist+1)//3*2
ans += l*(n-cum)
print(ans)

• Subtask 1: 90 / 100