Submission #19562667


Source Code Expand

Copy
k = int(input())
n = int(input())
ad = [tuple(map(int, input().split())) for i in range(n)]


def calc(cost):
    count = 0
    price = 0
    for a, d in ad:
        c = 1 + (cost - a) // d
        if c > 0:
            count += c
            price += a * c + d * (c - 1) * c // 2
    return count, price


ng = 0
ok = 10 ** 19

while ok - ng > 1:
    cost = (ng + ok) // 2
    count, price = calc(cost)
    if count < k:
        ng = cost
    else:
        ok = cost

count, price = calc(ok)
print(price - ok * (count - k))

Submission Info

Submission Time
Task C - 増築王高橋君
User ncrpy
Language Python (3.8.2)
Score 40
Code Size 554 Byte
Status TLE
Exec Time 2206 ms
Memory 21024 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 30 / 30 10 / 10 0 / 15 0 / 45
Status
AC × 2
AC × 14
AC × 26
AC × 34
TLE × 4
AC × 42
TLE × 10
Set Name Test Cases
Sample subtask0_sample-01.txt, subtask0_sample-02.txt
Subtask1 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Subtask4 subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask4_01.txt, subtask4_02.txt, subtask4_03.txt, subtask4_04.txt, subtask4_05.txt, subtask4_06.txt, subtask4_07.txt, subtask4_08.txt, subtask4_09.txt, subtask4_10.txt, subtask4_11.txt, subtask4_12.txt, subtask4_13.txt, subtask4_14.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt AC 25 ms 8920 KB
subtask0_sample-02.txt AC 25 ms 9052 KB
subtask1_01.txt AC 18 ms 8920 KB
subtask1_02.txt AC 20 ms 9144 KB
subtask1_03.txt AC 18 ms 9068 KB
subtask1_04.txt AC 19 ms 9024 KB
subtask1_05.txt AC 30 ms 9012 KB
subtask1_06.txt AC 18 ms 8920 KB
subtask1_07.txt AC 19 ms 9172 KB
subtask1_08.txt AC 33 ms 9208 KB
subtask1_09.txt AC 29 ms 9072 KB
subtask1_10.txt AC 35 ms 9088 KB
subtask1_11.txt AC 34 ms 8924 KB
subtask1_12.txt AC 21 ms 9024 KB
subtask2_01.txt AC 18 ms 9072 KB
subtask2_02.txt AC 38 ms 9032 KB
subtask2_03.txt AC 40 ms 9024 KB
subtask2_04.txt AC 20 ms 8912 KB
subtask2_05.txt AC 24 ms 9208 KB
subtask2_06.txt AC 149 ms 9360 KB
subtask2_07.txt AC 101 ms 9072 KB
subtask2_08.txt AC 110 ms 9176 KB
subtask2_09.txt AC 125 ms 9236 KB
subtask2_10.txt AC 149 ms 9360 KB
subtask2_11.txt AC 148 ms 9480 KB
subtask2_12.txt AC 86 ms 9064 KB
subtask3_01.txt AC 41 ms 9212 KB
subtask3_02.txt AC 19 ms 8912 KB
subtask3_03.txt AC 98 ms 9252 KB
subtask3_04.txt TLE 2206 ms 20820 KB
subtask3_05.txt AC 144 ms 9484 KB
subtask3_06.txt AC 118 ms 9352 KB
subtask3_07.txt AC 630 ms 11956 KB
subtask3_08.txt AC 1978 ms 18348 KB
subtask3_09.txt TLE 2206 ms 21024 KB
subtask3_10.txt TLE 2206 ms 21020 KB
subtask3_11.txt TLE 2206 ms 20724 KB
subtask3_12.txt AC 1252 ms 14536 KB
subtask4_01.txt TLE 2206 ms 20900 KB
subtask4_02.txt AC 25 ms 8912 KB
subtask4_03.txt AC 120 ms 9176 KB
subtask4_04.txt TLE 2206 ms 20712 KB
subtask4_05.txt AC 33 ms 9036 KB
subtask4_06.txt AC 25 ms 8924 KB
subtask4_07.txt AC 27 ms 9148 KB
subtask4_08.txt AC 25 ms 8916 KB
subtask4_09.txt TLE 2062 ms 18248 KB
subtask4_10.txt AC 35 ms 9144 KB
subtask4_11.txt TLE 2206 ms 20956 KB
subtask4_12.txt TLE 2206 ms 20716 KB
subtask4_13.txt TLE 2206 ms 20820 KB
subtask4_14.txt AC 24 ms 9080 KB