結果

問題 No.3293 Golden Cross
ユーザー kona0001
提出日時 2025-09-28 03:58:45
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,024 ms / 2,000 ms
コード長 1,965 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 8,192 KB
実行使用メモリ 26,496 KB
最終ジャッジ日時 2025-10-03 13:07:42
合計ジャッジ時間 29,456 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

h,w,k = gets.split.map(&:to_i)
A = h.times.map{gets.split.map(&:to_i)}
B = h.times.map{gets.split.map(&:to_i).map{|v|2.pow(v)}}

sum_row = Array.new(h,0)
sum_col = Array.new(w,0)
cost_row = Array.new(h){Array.new}
cost_col = Array.new(w){Array.new}
h.times do |i|
  w.times do |j|
    sum_row[i] += A[i][j]
    cost_row[i] << B[i][j]
    sum_col[j] += A[i][j]
    cost_col[j] << B[i][j]
  end
  cost_row[i].sort!
end
w.times do |i|
  cost_col[i].sort!
end

# 部分問題
def solve(a,b,c,a_cost,b_cost,c_cost,k)
  if a_cost <= b_cost && a_cost <= c_cost # a_cost が一番小さい時
    add_a = k/a_cost
    (a+add_a+b) * (a+add_a+c)
  elsif a_cost > b_cost && a_cost > c_cost # a_cost が単独で一番大きい時
    b_opt = ((a+c)*c_cost - (a+b)*b_cost + k) / (2*b_cost)
    kouho = [0,b_opt,b_opt+1,k/b_cost]
    max = 0
    kouho.each do |add_b|
      next if add_b < 0 || k/b_cost < add_b
      rest_k = k - add_b * b_cost
      add_c = rest_k/c_cost
      val = (a+b+add_b) * (a+c+add_c)
      max = val if max < val
    end
    max
  else # a_cost より小さい値が 1 つだけある時 (c_cost)
    a_opt = ((a+c)*c_cost + (a+b)*(c_cost-a_cost) + k) / (2*(a_cost-c_cost))
    kouho = [0,a_opt,a_opt+1,k/a_cost]
    max = 0
    kouho.each do |add_a|
      next if add_a < 0 || k/a_cost < add_a
      rest_k = k - add_a * a_cost
      add_c = rest_k/c_cost
      val = (a+add_a+b) * (a+add_a+c+add_c)
      max = val if max < val
    end
    max
  end
end

max = 0
h.times do |i|
  w.times do |j|
    a = A[i][j]
    a_cost = B[i][j]
    b = sum_row[i] - a
    b_cost = a_cost == cost_row[i][0] ? cost_row[i][1] : cost_row[i][0]
    c = sum_col[j] - a
    c_cost = a_cost == cost_col[j][0] ? cost_col[j][1] : cost_col[j][0]
    if b_cost < c_cost # b_costの方が絶対に大きくなるようにする
      b,c = c,b
      b_cost,c_cost = c_cost,b_cost
    end
    v = solve(a,b,c,a_cost,b_cost,c_cost,k)
    max = v if max < v
  end
end
puts max
0