結果

問題 No.2840 RGB Plates
コンテスト
ユーザー tomerun
提出日時 2024-08-09 22:40:32
言語 Crystal
(1.14.0)
結果
AC  
実行時間 886 ms / 2,000 ms
コード長 621 bytes
コンパイル時間 11,851 ms
コンパイル使用メモリ 293,492 KB
実行使用メモリ 263,748 KB
最終ジャッジ日時 2024-08-18 01:01:06
合計ジャッジ時間 33,009 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF = 1 << 29

n = read_line.to_i
a = read_line.split.map(&.to_i)
l = 50000000 // n
dp = Array.new(l * 2 + 1, INF)
dp2 = Array.new(l * 2 + 1, INF)
ans = INF
n.times do |i|
  dp2.fill(INF)
  dp2[l + a[i]] = a[i]
  dp2[l - a[i]] = a[i]
  dp.size.times do |j|
    next if dp[j] == INF
    dp2[j] = {dp2[j], dp[j]}.min
    if j - a[i] >= 0
      dp2[j - a[i]] = {dp2[j - a[i]], dp[j] + a[i]}.min
    end
    if j + a[i] < dp.size
      dp2[j + a[i]] = {dp2[j + a[i]], dp[j] + a[i]}.min
    end
  end
  dp, dp2 = dp2, dp
  ans = {ans, dp[l]}.min
end
sum = a.sum
if ans == sum || ans == INF
  puts -1
else
  puts sum - ans
end
0