結果
問題 |
No.2046 Ans Mod? Mod Ans!
|
ユーザー |
![]() |
提出日時 | 2022-08-19 22:28:06 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 93 ms / 4,000 ms |
コード長 | 484 bytes |
コンパイル時間 | 16,011 ms |
コンパイル使用メモリ | 295,420 KB |
実行使用メモリ | 28,672 KB |
最終ジャッジ日時 | 2024-12-16 08:24:37 |
合計ジャッジ時間 | 17,486 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
n = read_line.to_i a = read_line.split.map(&.to_i64).sort max = a.max sum = Array.new(max * 3 + 1, 0i64) cnt = Array.new(max * 3 + 1, 0i64) ans = 0i64 n.times do |i| v = a[i] sum[v] = v cnt[v] = 1 ans += v * (n - 1 - i) end 1.upto(sum.size - 1) do |i| sum[i] += sum[i - 1] cnt[i] += cnt[i - 1] end a.each do |v| cur = v while cur <= max + v s = sum[cur + v - 1] - sum[cur] c = cnt[cur + v - 1] - cnt[cur] ans -= s - c * cur cur += v end end puts ans