結果

問題 No.21 平均の差
ユーザー vjudge1
提出日時 2025-09-08 11:08:51
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 1,059 bytes
コンパイル時間 14,912 ms
コンパイル使用メモリ 310,492 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-09-08 11:09:07
合計ジャッジ時間 11,903 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = gets.not_nil!.to_i
k = gets.not_nil!.to_i
num = Array(Int32).new(n + 1, 0)

(1..n).each do |i|
  num[i] = gets.not_nil!.to_i
end

sum = Array(Int32).new(10, 0)
cnt = Array(Int32).new(10, 0)
ans = 0

def solve(idx, sz, n, k, num, sum, cnt, ans)
  if idx == n + 1
    if sz == k
      now_min = Int32::MAX
      now_max = 0
      
      (1..k).each do |i|
        now = sum[i]
        (1..9).each do |j|
          if j != cnt[i]
            now *= j
          end
        end
        
        now_min = Math.min(now_min, now)
        now_max = Math.max(now_max, now)
      end
      
      p = 1
      (1..9).each { |i| p *= i }
      
      diff = now_max - now_min
      if diff % p == 0
        ans = Math.max(ans, diff // p)
      else
        ans = Math.max(ans, diff // p + 1)
      end
    end
    return
  end
  
  (1..Math.min(sz + 1, k)).each do |i|
    sum[i] += num[idx]
    cnt[i] += 1
    solve(idx + 1, Math.max(sz, i), n, k, num, sum, cnt, ans)
    cnt[i] -= 1
    sum[i] -= num[idx]
  end
end

solve(1, 0, n, k, num, sum, cnt, ans)
puts ans
0