結果

問題 No.2840 RGB Plates
ユーザー tomeruntomerun
提出日時 2024-08-09 22:40:32
言語 Crystal
(1.11.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 191 ms
159,416 KB
testcase_01 AC 283 ms
263,724 KB
testcase_02 AC 146 ms
74,108 KB
testcase_03 AC 847 ms
6,944 KB
testcase_04 AC 289 ms
263,748 KB
testcase_05 AC 769 ms
6,940 KB
testcase_06 AC 146 ms
63,044 KB
testcase_07 AC 149 ms
62,960 KB
testcase_08 AC 143 ms
58,752 KB
testcase_09 AC 144 ms
51,724 KB
testcase_10 AC 88 ms
6,940 KB
testcase_11 AC 145 ms
62,968 KB
testcase_12 AC 864 ms
6,944 KB
testcase_13 AC 869 ms
6,944 KB
testcase_14 AC 855 ms
6,944 KB
testcase_15 AC 860 ms
6,944 KB
testcase_16 AC 872 ms
6,940 KB
testcase_17 AC 864 ms
6,944 KB
testcase_18 AC 869 ms
6,944 KB
testcase_19 AC 867 ms
6,940 KB
testcase_20 AC 870 ms
6,940 KB
testcase_21 AC 854 ms
6,940 KB
testcase_22 AC 863 ms
6,940 KB
testcase_23 AC 870 ms
6,944 KB
testcase_24 AC 840 ms
6,944 KB
testcase_25 AC 864 ms
6,944 KB
testcase_26 AC 864 ms
6,944 KB
testcase_27 AC 872 ms
6,944 KB
testcase_28 AC 886 ms
6,940 KB
testcase_29 AC 872 ms
6,944 KB
testcase_30 AC 864 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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