結果

問題 No.3051 Make All Divisible
ユーザー suisen
提出日時 2025-01-18 16:03:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 475 ms / 2,000 ms
コード長 761 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 76,940 KB
最終ジャッジ日時 2025-06-20 02:20:21
合計ジャッジ時間 5,625 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

# correct

from heapq import heappush, heappushpop


def solve(n: int, k: int, a: list[int]) -> None:
    if sum(a) % k:
        print(-1)
        return

    pq: list[int] = []
    threshold = k * (k - 1) // 2
    for i in range(n):
        q = (max(0, a[i] - threshold) + (k - 1)) // k
        a[i] -= q * k
        heappush(pq, -a[i])

    INF = 1 << 30
    ans = INF
    t = sum(a) // k
    while True:
        e = -pq[0]
        if e <= t:
            ans = t
        e -= k
        if e < 0:
            break
        heappushpop(pq, -e)
        t -= 1

    if ans == INF:
        print(-1)
    else:
        print(ans)


t = int(input())

for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    solve(n, k, a)
0