Submission #19562500


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_min = 0
    count_same = 0
    price = 0
    for a, d in ad:
        c = 1 + (cost - a - 1) // d
        if c > 0:
            count_min += c
            price += a * c + d * (c - 1) * c // 2
            if (cost - a) % d == 0:
                count_same += 1
    return count_min, count_same, price


ng = 0
ok = 10 ** 19

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

count_min, count_same, price = calc(ok)
print(price + ok * (k - count_min))

Submission Info

Submission Time
Task C - 増築王高橋君
User ncrpy
Language Python (3.8.2)
Score 30
Code Size 725 Byte
Status WA
Exec Time 2206 ms
Memory 20956 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 30 / 30 0 / 10 0 / 15 0 / 45
Status
AC × 2
AC × 14
AC × 25
WA × 1
AC × 31
WA × 2
TLE × 5
AC × 39
WA × 2
TLE × 11
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 19 ms 9156 KB
subtask0_sample-02.txt AC 22 ms 9160 KB
subtask1_01.txt AC 24 ms 9016 KB
subtask1_02.txt AC 25 ms 8916 KB
subtask1_03.txt AC 20 ms 9004 KB
subtask1_04.txt AC 26 ms 9052 KB
subtask1_05.txt AC 26 ms 9128 KB
subtask1_06.txt AC 23 ms 8896 KB
subtask1_07.txt AC 28 ms 8900 KB
subtask1_08.txt AC 29 ms 9144 KB
subtask1_09.txt AC 29 ms 8900 KB
subtask1_10.txt AC 36 ms 9012 KB
subtask1_11.txt AC 29 ms 9068 KB
subtask1_12.txt AC 24 ms 9020 KB
subtask2_01.txt AC 20 ms 8900 KB
subtask2_02.txt AC 43 ms 8904 KB
subtask2_03.txt AC 42 ms 9156 KB
subtask2_04.txt AC 29 ms 9072 KB
subtask2_05.txt AC 33 ms 9008 KB
subtask2_06.txt AC 179 ms 9516 KB
subtask2_07.txt AC 120 ms 9036 KB
subtask2_08.txt AC 134 ms 9332 KB
subtask2_09.txt WA 152 ms 9224 KB
subtask2_10.txt AC 179 ms 9452 KB
subtask2_11.txt AC 182 ms 9492 KB
subtask2_12.txt AC 107 ms 9204 KB
subtask3_01.txt AC 42 ms 9068 KB
subtask3_02.txt AC 25 ms 9160 KB
subtask3_03.txt AC 120 ms 9056 KB
subtask3_04.txt TLE 2206 ms 20696 KB
subtask3_05.txt WA 174 ms 9492 KB
subtask3_06.txt AC 142 ms 9328 KB
subtask3_07.txt AC 790 ms 11928 KB
subtask3_08.txt TLE 2206 ms 18496 KB
subtask3_09.txt TLE 2206 ms 20956 KB
subtask3_10.txt TLE 2206 ms 20692 KB
subtask3_11.txt TLE 2206 ms 20936 KB
subtask3_12.txt AC 1576 ms 14628 KB
subtask4_01.txt TLE 2206 ms 20800 KB
subtask4_02.txt AC 24 ms 9016 KB
subtask4_03.txt AC 141 ms 9144 KB
subtask4_04.txt TLE 2206 ms 20848 KB
subtask4_05.txt AC 37 ms 9020 KB
subtask4_06.txt AC 27 ms 9060 KB
subtask4_07.txt AC 19 ms 9056 KB
subtask4_08.txt AC 25 ms 8904 KB
subtask4_09.txt TLE 2206 ms 18236 KB
subtask4_10.txt AC 34 ms 8916 KB
subtask4_11.txt TLE 2206 ms 20824 KB
subtask4_12.txt TLE 2206 ms 20876 KB
subtask4_13.txt TLE 2206 ms 20696 KB
subtask4_14.txt AC 22 ms 8900 KB