Submission #19562761


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 ** 11

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 100
Code Size 554 Byte
Status AC
Exec Time 1436 ms
Memory 20880 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 30 / 30 10 / 10 15 / 15 45 / 45
Status
AC × 2
AC × 14
AC × 26
AC × 38
AC × 52
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 27 ms 9084 KB
subtask0_sample-02.txt AC 23 ms 9152 KB
subtask1_01.txt AC 21 ms 9084 KB
subtask1_02.txt AC 18 ms 9024 KB
subtask1_03.txt AC 19 ms 9092 KB
subtask1_04.txt AC 24 ms 9216 KB
subtask1_05.txt AC 25 ms 8924 KB
subtask1_06.txt AC 18 ms 9088 KB
subtask1_07.txt AC 21 ms 9152 KB
subtask1_08.txt AC 22 ms 9032 KB
subtask1_09.txt AC 25 ms 9088 KB
subtask1_10.txt AC 23 ms 9036 KB
subtask1_11.txt AC 26 ms 9032 KB
subtask1_12.txt AC 19 ms 8920 KB
subtask2_01.txt AC 22 ms 9084 KB
subtask2_02.txt AC 32 ms 8928 KB
subtask2_03.txt AC 33 ms 8928 KB
subtask2_04.txt AC 19 ms 8916 KB
subtask2_05.txt AC 28 ms 8924 KB
subtask2_06.txt AC 87 ms 9600 KB
subtask2_07.txt AC 63 ms 9184 KB
subtask2_08.txt AC 70 ms 9312 KB
subtask2_09.txt AC 75 ms 9244 KB
subtask2_10.txt AC 88 ms 9364 KB
subtask2_11.txt AC 88 ms 9540 KB
subtask2_12.txt AC 61 ms 9308 KB
subtask3_01.txt AC 31 ms 9164 KB
subtask3_02.txt AC 21 ms 8928 KB
subtask3_03.txt AC 65 ms 9196 KB
subtask3_04.txt AC 1178 ms 20796 KB
subtask3_05.txt AC 85 ms 9492 KB
subtask3_06.txt AC 74 ms 9372 KB
subtask3_07.txt AC 328 ms 12040 KB
subtask3_08.txt AC 1004 ms 18484 KB
subtask3_09.txt AC 1250 ms 20564 KB
subtask3_10.txt AC 1205 ms 20572 KB
subtask3_11.txt AC 1235 ms 20568 KB
subtask3_12.txt AC 657 ms 14856 KB
subtask4_01.txt AC 1304 ms 20880 KB
subtask4_02.txt AC 25 ms 9220 KB
subtask4_03.txt AC 77 ms 9496 KB
subtask4_04.txt AC 1353 ms 20568 KB
subtask4_05.txt AC 33 ms 9220 KB
subtask4_06.txt AC 18 ms 9088 KB
subtask4_07.txt AC 26 ms 9092 KB
subtask4_08.txt AC 20 ms 8920 KB
subtask4_09.txt AC 1110 ms 18268 KB
subtask4_10.txt AC 29 ms 9096 KB
subtask4_11.txt AC 1409 ms 20676 KB
subtask4_12.txt AC 1433 ms 20696 KB
subtask4_13.txt AC 1436 ms 20816 KB
subtask4_14.txt AC 20 ms 9156 KB