結果
問題 | No.1538 引きこもりさんは引き算が得意。 |
ユーザー |
![]() |
提出日時 | 2022-09-11 10:33:19 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 1,077 bytes |
コンパイル時間 | 397 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 17,408 KB |
最終ジャッジ日時 | 2024-11-27 19:11:33 |
合計ジャッジ時間 | 7,306 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
コンパイルメッセージ
Syntax OK
ソースコード
N, K = gets.split.map(&:to_i)A = gets.split.map(&:to_i)def dfs(i, e, min, max, sum, memo)if i == eif min == -1 && max == 1memo[3][sum] = trueelsif min == -1memo[2][sum] = trueelsif max == 1memo[1][sum] = trueelsememo[0][sum] = trueendelsedfs(i + 1, e, -1, max, sum - A[i], memo)dfs(i + 1, e, min, max, sum, memo)dfs(i + 1, e, min, 1, sum + A[i], memo)endendmemo1 = Hash.new { |h, k| h[k] = {} }memo2 = Hash.new { |h, k| h[k] = {} }mid = N / 2dfs(0, mid, 0, 0, 0, memo1)dfs(mid, N, 0, 0, 0, memo2)if A.count(K) > 0puts 'Yes'exitendif memo1[3][K] || memo2[3][K]puts 'Yes'exitend1.upto(3) do |t|memo1[t].each do |k, v|case twhen 1if memo2[2][K - k] || memo2[3][K - k]puts 'Yes'exitendwhen 2if memo2[1][K - k] || memo2[3][K - k]puts 'Yes'exitendwhen 3if memo2[1][K - k] || memo2[2][K - k] || memo2[3][K - k]puts 'Yes'exitendendendendputs 'No'