結果

問題 No.3293 Golden Cross
コンテスト
ユーザー kidodesu
提出日時 2025-10-03 23:09:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 714 ms / 2,000 ms
コード長 1,731 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 83,908 KB
最終ジャッジ日時 2025-10-03 23:09:37
合計ジャッジ時間 18,084 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

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) // C[ca]
            a1 = a + (k - C[cb] * m1) // C[ca]
        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] * m) // C[ca]
    #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)
0