結果

問題 No.3293 Golden Cross
コンテスト
ユーザー kona0001
提出日時 2025-09-09 04:16:00
言語 Ruby
(3.4.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,671 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 8,064 KB
実行使用メモリ 26,368 KB
最終ジャッジ日時 2025-10-03 13:04:10
合計ジャッジ時間 7,325 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 1
other WA * 1 RE * 4 TLE * 1 -- * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
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)}

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

# Z を決め打ちした時の部分問題
# (a + b) * (a + c) に対応
def calc(a,b,c,y,z,k)
  b_opt = (z*(a+c) - y*(a+b) + k) / (2*y)
  kouho = [0,b_opt,b_opt+1,k/y]
  max = 0
  kouho.each do |v|
    next if v < 0 || k/y < v
    rest_k = k - v*y
    c_add = rest_k/z
    val = (a+b+v) * (a+c+c_add)
    max = val if max < val
  end
  max
end

# 三分探索
def solve(x,y,z,x_cost,y_cost,z_cost,k)
  l = 0
  r = k / z_cost
  while r - l > 2 #精度
    dif = (r - l) / 3
    t1,t2 = l+dif,r-dif
    s1 = calc(z+t1,x,y,x_cost,y_cost,k-t1*z_cost)
    s2 = calc(z+t2,x,y,x_cost,y_cost,k-t2*z_cost)
    if s1 < s2 #上に凸
      l = t1
    else
      r = t2
    end
  end
  #puts l
  max = 0
  3.times do |i|
    t = l + i
    next if t*z_cost > k
    v = calc(z+t,x,y,x_cost,y_cost,k-t*z_cost)
    max = v if max < v
  end
  max
end

max = 0
h.times do |i|
  ai = a[i]
  bi = b[i]
  cost_rowi = cost_row[i]
  w.times do |j|
    z = ai[j]
    z_cost = bi[j]
    x = sum_row[i] - z
    x_cost = z_cost == cost_rowi[0] ? cost_rowi[1] : cost_rowi[0]
    y = sum_col[j] - z
    y_cost = z_cost == cost_col[j][0] ? cost_col[j][1] : cost_col[j][0]
    v = solve(x,y,z,x_cost,y_cost,z_cost,k)
    max = v if max < v
  end
end
puts max
0