結果

問題 No.3293 Golden Cross
ユーザー kona0001
提出日時 2025-09-09 03:42:21
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 2,023 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 8,064 KB
実行使用メモリ 13,440 KB
最終ジャッジ日時 2025-10-03 13:03:47
合計ジャッジ時間 7,019 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def assert f
  unless f
    puts "Error!: Constraint Violation"
    exit
  end
end

h,w,k = gets.split.map(&:to_i)
assert(2 <= h && h <= 300)
assert(2 <= w && w <= 300)
assert(0 <= k && k <= 2**30)

a = h.times.map{gets.split.map(&:to_i)}
a.each do |row|
  row.each do |v|
    assert(1 <= v && v <= 10**6)
  end
end

hash = Hash.new(0)
31.times do |i|
  hash[2**i] = 1
end
b = h.times.map{gets.split.map(&:to_i)}
b.each do |row|
  row.each do |v|
    assert(1 <= v && v <= 2**30)
    assert(hash[v] == 1)
  end
end

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
  max = 0
  4.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|
  w.times do |j|
    z = a[i][j]
    z_cost = b[i][j]
    x = sum_row[i] - z
    x_cost = z_cost == cost_row[i][0] ? cost_row[i][1] : cost_row[i][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