oj.uz

Submission #550325

# Submission time Handle Problem Language Result Execution time Memory
550325 2022-04-17T21:13:58 Z sealnot123 City (BOI06_city) Python 3
90 / 100
 1000 ms 3828 KB 
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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2900 KB Output is correct
2 Correct 13 ms 2904 KB Output is correct
3 Correct 14 ms 2900 KB Output is correct
4 Correct 314 ms 3088 KB Output is correct
5 Correct 13 ms 2900 KB Output is correct
6 Correct 14 ms 2900 KB Output is correct
7 Execution timed out 1093 ms 3828 KB Time limit exceeded
8 Correct 363 ms 3088 KB Output is correct
9 Correct 127 ms 2972 KB Output is correct
10 Correct 18 ms 2896 KB Output is correct