結果
問題 |
No.2046 Ans Mod? Mod Ans!
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:57:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,545 ms / 4,000 ms |
コード長 | 958 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 81,820 KB |
実行使用メモリ | 119,608 KB |
最終ジャッジ日時 | 2025-03-26 15:57:41 |
合計ジャッジ時間 | 8,650 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) A = list(map(int, data[1:N+1])) A.sort() suffix_sum = [0] * (N + 1) for i in range(N-1, -1, -1): suffix_sum[i] = suffix_sum[i+1] + A[i] total = 0 for i in range(N): y = A[i] k = N - (i + 1) if k == 0: continue sum_x_gt_y = suffix_sum[i+1] max_x = A[-1] q_max = max_x // y sum_floor = 0 q = 1 while q <= q_max: low = q * y high = (q + 1) * y left = bisect.bisect_left(A, low, i + 1, N) right = bisect.bisect_left(A, high, i + 1, N) count = right - left sum_floor += q * count q += 1 sum_mod = sum_x_gt_y - y * sum_floor contrib = y * k - sum_mod total += contrib print(total) if __name__ == '__main__': main()