結果
問題 |
No.3293 Golden Cross
|
ユーザー |
![]() |
提出日時 | 2025-10-03 23:06:56 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,705 bytes |
コンパイル時間 | 590 ms |
コンパイル使用メモリ | 82,420 KB |
実行使用メモリ | 84,520 KB |
最終ジャッジ日時 | 2025-10-03 23:07:09 |
合計ジャッジ時間 | 12,332 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 WA * 23 RE * 1 |
ソースコード
h, w, k = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(h)] B = [list(map(int, input().split())) for _ in range(h)] H_a = [sum(A[i]) for i in range(h)] W_a = [0] * w for x in range(w): t = 0 for y in range(h): t += A[y][x] W_a[x] = t inf = float("INF") H_b = [min(B[i]) for i in range(h)] W_b = [inf] * w for x in range(w): for y in range(h): W_b[x] = min(W_b[x], B[y][x]) C = [1] for _ in range(40): C.append(C[-1] * 2) def main(a, b, ca, cb, fa, fb): if fa and fb: a += k // C[ca] b += k // C[cb] return a * b f = fa + fb if ca > cb: a, b, ca, cb = b, a, cb, ca l = -1 r = k // C[cb] while r - l > 1: m0 = (l + r) >> 1 m1 = m0 + 1 b0 = b + m0 b1 = b + m1 if f: a0 = a + (k - C[cb] * m0) // C[ca] + m0 a1 = a + (k - C[cb] * m1) // C[ca] + m1 else: a0 = a + (k - C[cb] * m0) a1 = a + (k - C[cb] * m0) if a1 * b1 >= a0 * b0: l = m0 else: r = m0 m = l + 1 b += m if f: a += (k - C[cb] * m) // C[ca] + m else: a += (k - C[cb] * m0) #print(m, "m", a, b, (k - C[cb] * m), C[ca], (k - C[cb] * m) // C[ca], (k - C[cb] * m) // C[ca] + m) return a * b ans = 0 for y in range(h): for x in range(w): h_a = H_a[y] w_a = W_a[x] h_b = H_b[y] w_b = W_b[x] h_f = w_f = 0 if B[y][x] == h_b: h_f = 1 if B[y][x] == w_b: w_f = 1 tmp = main(h_a, w_a, h_b, w_b, h_f, w_f) #print(tmp) ans = max(ans, tmp) print(ans)