結果
問題 | No.3054 Modulo Inequalities |
ユーザー |
|
提出日時 | 2025-01-18 16:18:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 711 ms / 2,500 ms |
コード長 | 607 bytes |
コンパイル時間 | 426 ms |
コンパイル使用メモリ | 82,544 KB |
実行使用メモリ | 108,416 KB |
最終ジャッジ日時 | 2025-02-02 13:29:41 |
合計ジャッジ時間 | 15,983 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
# correct M = 10**6 + 10 n = int(input()) # -M, ..., -1, 0, 1, ..., M # c[i] = weight of i - M c = [0] * (2 * M + 1) for _ in range(n): a, b = map(int, input().split()) c[M + a] += 1 c[M + b] -= 1 c[M + a - b] -= 1 # prefix sum c.insert(0, 0) for i in range(2 * M + 1): c[i + 1] += c[i] max_f, argmax = -1, 0 for m in range(1, M): # max{k | k * m <= M} max_k = M // m f_m = -n * max_k # sum C(-tm), ..., C(-m), C(0), C(m), ..., C(tm) for k in range(-max_k, max_k + 1): f_m -= c[M + k * m] if f_m > max_f: max_f, argmax = f_m, m print(argmax)