結果

問題 No.2227 King Kraken's Attack
ユーザー lam6er
提出日時 2025-04-15 22:55:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 311 ms / 2,000 ms
コード長 2,844 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 75,916 KB
最終ジャッジ日時 2025-04-15 22:57:34
合計ジャッジ時間 4,844 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    H, W, L_A, L_B, K_A, K_B = map(int, sys.stdin.readline().split())
    
    min_sum = float('inf')
    
    # Case 1: cover all rows and columns
    A1 = (H + L_A - 1) // L_A
    B1 = (W + L_B - 1) // L_B
    sum1 = A1 + B1
    min_sum = min(min_sum, sum1)
    
    # Iterate A up to a reasonable limit
    max_A = (H + L_A - 1) // L_A + 200  # Adding a buffer to cover possible cases
    max_A = min(max_A, 10**6)
    for A in range(0, max_A + 1):
        U_A = max(H - A * L_A, 0)
        # Compute B_case1: B >= B0 and provides enough extras
        B0 = (W + L_B - 1) // L_B
        required_case1 = U_A * W
        needed_from_B = max(0, required_case1 - A * K_A)
        if K_B == 0:
            if needed_from_B > 0:
                B_case1 = float('inf')
            else:
                B_case1 = B0
        else:
            B_needed = (needed_from_B + K_B - 1) // K_B if needed_from_B > 0 else 0
            B_case1 = max(B0, B_needed)
        sum_case1 = A + B_case1 if B_case1 != float('inf') else float('inf')
        
        # Compute B_case2: B < B0 and provides enough extras
        B_case2 = float('inf')
        denominator = K_B + L_B * (H - U_A)
        if denominator == 0:
            if (H * W - A * K_A) <= 0:
                B_candidate = 0
                if B_candidate * L_B < W:
                    sum_case2_candidate = A + B_candidate
                    B_case2 = B_candidate
        else:
            needed = H * W - A * K_A
            if needed <= 0:
                B_candidate = 0
                if B_candidate * L_B < W:
                    B_case2 = B_candidate
            else:
                B_candidate = (needed + denominator - 1) // denominator
                B_max = (W - 1) // L_B
                B_candidate = min(B_candidate, B_max)
                if B_candidate >= 0:
                    B = B_candidate
                    U_B = W - B * L_B
                    required = U_A * W + U_B * H - U_A * U_B
                    if A * K_A + B * K_B >= required:
                        B_case2 = B
                    else:
                        B += 1
                        if B <= B_max:
                            U_B = W - B * L_B
                            required = U_A * W + U_B * H - U_A * U_B
                            if A * K_A + B * K_B >= required:
                                B_case2 = B
        if B_case2 != float('inf'):
            sum_case2 = A + B_case2
            # Verify if B_case2 * L_B < W
            if B_case2 * L_B >= W:
                sum_case2 = float('inf')
        else:
            sum_case2 = float('inf')
        
        current_sum = min(sum_case1, sum_case2)
        if current_sum < min_sum:
            min_sum = current_sum
    
    print(min_sum)
    
if __name__ == '__main__':
    main()
0