結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー tomerun
提出日時 2026-07-10 22:16:38
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,443 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,393 ms
コンパイル使用メモリ 338,036 KB
実行使用メモリ 14,080 KB
最終ジャッジ日時 2026-07-10 22:17:01
合計ジャッジ時間 14,688 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 22 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, m, k = read_line.split.map(&.to_i)
all = n * (n - 1) // 2
if k > all - m
  puts "No"
  exit
end
dp = Array.new(k + 1) { Array.new(n + 1) { Array.new(n + 1, -1) } }
prev = Array.new(k + 1) { Array.new(n + 1) { Array.new(n + 1, -1) } }
dp[0][1][1] = 0
k.times do |i|
  1.upto(n - 1) do |tc|
    1.upto(tc) do |pc|
      1.upto(n - tc) do |cc|
        next if dp[i][tc][pc] < 0
        cnt = dp[i][tc][pc] + pc * cc + cc * (cc - 1) // 2
        if dp[i + 1][tc + cc][cc] < cnt
          dp[i + 1][tc + cc][cc] = cnt
          prev[i + 1][tc + cc][cc] = pc
        end
      end
    end
  end
end
mi = (0..n).max_by { |i| dp[k][n][i] }
max = dp[k][n][mi]
# puts "max:#{max}"
if all - m <= max
  cnts = [mi]
  left = n
  layer = Array.new(n, 0)
  k.downto(1) do |i|
    # puts "i:#{i} left:#{left} pc:#{cnts[-1]}"
    cnts[-1].times do |j|
      layer[left - 1 - j] = i
    end
    pc = prev[i][left][cnts[-1]]
    left -= cnts[-1]
    cnts << pc
  end
  puts "Yes"
  guard = Array.new(n) { Array.new(n, false) }
  removed = 0
  n.times do |i|
    if i > 0 && layer[i] == layer[i - 1] + 1
      guard[i][i - 1] = true
    end
    i.times do |j|
      if (layer[i] - layer[j]).abs > 1
        guard[i][j] = true
        puts "#{j} #{i}"
        removed += 1
      end
    end
  end
  n.times do |i|
    i.times do |j|
      if removed < m && !guard[i][j]
        puts "#{j} #{i}"
        removed += 1
      end
    end
  end
else
  puts "No"
end
0