結果
問題 | No.1495 パンの仕入れ |
ユーザー |
![]() |
提出日時 | 2021-04-25 02:52:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 478 ms / 2,000 ms |
コード長 | 1,227 bytes |
コンパイル時間 | 357 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 84,224 KB |
最終ジャッジ日時 | 2024-07-18 21:26:15 |
合計ジャッジ時間 | 17,360 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
T = int(input()) inf = int(2e18) for _ in range(T): N, M, K = map(int, input().split()) x = [0]*M y = [0]*M for i in range(M): x[i], y[i] = map(int, input().split()) cnt = [0]*N mem = [0]*N for i in range(M): x[i] -= 1 cnt[x[i]] += 2 # (x-y)^2-(x-(y-1))^2 = 2x-2y-1 mem[x[i]] -= 2*y[i]+1 left = -inf right = inf while left+1 < right: mid = (right+left)//2 cnt2 = 0 for i in range(N): if cnt[i] == 0: if 0 <= mid: cnt2 += inf else: # ax+mem[i] ≤ mid # ax ≤ mid-mem[i] cnt2 += max(0, (mid-mem[i])//cnt[i]) if cnt2 > K: break if cnt2 <= K: left = mid else: right = mid ans = 0 flag = False num = [0]*N cnt2 = 0 for i in range(N): if cnt[i] == 0: flag = True else: num[i] = max(0, (left-mem[i])//cnt[i]) cnt2 += num[i] for i in range(M): ans += (num[x[i]]-y[i])*(num[x[i]]-y[i]) if flag and right > 0: cnt2 = K ans += (K-cnt2)*right print(ans)