Submission #75672705

Source Code Expand

# K<=10**18
# 2**10=10**3より
# K<=2**60
# heapqの貪欲法はだめ
# 答えを2分探索？


N, K = map(int, input().split())
A = list(map(int, input().split()))
L = 10**18


# 全てX以上にできるか
def check(x):
    cnt = 0
    added = 0
    for i in range(N - 1, -1, -1):
        cur = A[i] + added
        if cur < x:
            y = x - cur
            ops = (y + i) // (i + 1)  # 切り上げ除算（整数）
            cnt += ops
            if cnt > K:
                return False
            added += ops
    return True


l = 0
r = L
# l<rなら、r=l+1の時にm=lとなり無限ループになるので注意
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Submission Info

Submission Time
Task D - Raise Minimum
User msd7
Language Python (PyPy 3.11-v7.3.20)
Score 0
Code Size 779 Byte
Status WA
Exec Time 231 ms
Memory 143272 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
WA × 3
AC × 3
WA × 44
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_corner_00.txt, 01_corner_01.txt, 01_corner_02.txt, 01_corner_03.txt, 01_corner_04.txt, 01_corner_05.txt, 01_corner_06.txt, 01_corner_07.txt, 01_corner_08.txt, 01_corner_09.txt, 01_corner_10.txt, 02_hack_00.txt, 02_hack_01.txt, 02_hack_02.txt, 02_hack_03.txt, 02_hack_04.txt, 02_hack_05.txt, 02_hack_06.txt, 02_hack_07.txt, 02_hack_08.txt, 02_hack_09.txt, 02_hack_10.txt, 02_hack_11.txt, 02_hack_12.txt, 03_random_00.txt, 03_random_01.txt, 03_random_02.txt, 03_random_03.txt, 03_random_04.txt, 03_random_05.txt, 03_random_06.txt, 03_random_07.txt, 03_random_08.txt, 03_random_09.txt, 03_random_10.txt, 03_random_11.txt, 03_random_12.txt, 03_random_13.txt, 03_random_14.txt, 03_random_15.txt, 03_random_16.txt, 03_random_17.txt, 03_random_18.txt, 03_random_19.txt
Case Name Status Exec Time Memory
00_sample_00.txt WA 52 ms 79768 KiB
00_sample_01.txt WA 51 ms 79580 KiB
00_sample_02.txt WA 51 ms 79432 KiB
01_corner_00.txt AC 51 ms 79464 KiB
01_corner_01.txt WA 75 ms 124104 KiB
01_corner_02.txt WA 52 ms 79600 KiB
01_corner_03.txt WA 119 ms 136676 KiB
01_corner_04.txt WA 177 ms 125592 KiB
01_corner_05.txt WA 177 ms 125656 KiB
01_corner_06.txt WA 188 ms 130524 KiB
01_corner_07.txt WA 203 ms 137348 KiB
01_corner_08.txt WA 193 ms 136860 KiB
01_corner_09.txt WA 190 ms 130344 KiB
01_corner_10.txt WA 189 ms 130520 KiB
02_hack_00.txt WA 52 ms 79476 KiB
02_hack_01.txt WA 52 ms 79580 KiB
02_hack_02.txt AC 52 ms 79648 KiB
02_hack_03.txt AC 51 ms 79412 KiB
02_hack_04.txt WA 88 ms 132824 KiB
02_hack_05.txt WA 90 ms 130528 KiB
02_hack_06.txt WA 68 ms 94332 KiB
02_hack_07.txt WA 123 ms 126376 KiB
02_hack_08.txt WA 143 ms 133700 KiB
02_hack_09.txt WA 93 ms 106240 KiB
02_hack_10.txt WA 177 ms 143272 KiB
02_hack_11.txt WA 102 ms 107132 KiB
02_hack_12.txt WA 106 ms 108584 KiB
03_random_00.txt WA 219 ms 136192 KiB
03_random_01.txt WA 215 ms 137504 KiB
03_random_02.txt WA 190 ms 136408 KiB
03_random_03.txt WA 91 ms 99720 KiB
03_random_04.txt WA 220 ms 136468 KiB
03_random_05.txt WA 136 ms 120952 KiB
03_random_06.txt WA 184 ms 136424 KiB
03_random_07.txt WA 68 ms 101200 KiB
03_random_08.txt WA 216 ms 136408 KiB
03_random_09.txt WA 96 ms 104560 KiB
03_random_10.txt WA 119 ms 136336 KiB
03_random_11.txt WA 109 ms 119836 KiB
03_random_12.txt WA 226 ms 136600 KiB
03_random_13.txt WA 150 ms 128064 KiB
03_random_14.txt WA 231 ms 136508 KiB
03_random_15.txt WA 112 ms 128100 KiB
03_random_16.txt WA 220 ms 136484 KiB
03_random_17.txt WA 217 ms 136452 KiB
03_random_18.txt WA 218 ms 136488 KiB
03_random_19.txt WA 216 ms 136712 KiB