結果

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

ソースコード

diff # 

import math

def main():
    H, W, L_A, L_B, K_A, K_B = map(int, input().split())
    N = H * W
    ans = float('inf')
    
    # Case 2: All via rows and columns
    case2 = ( (H + L_A - 1) // L_A ) + ( (W + L_B - 1) // L_B )
    ans = min(ans, case2)
    
    # Case 1: All via K selections
    if K_A == 0 and K_B == 0:
        pass  # Impossible
    else:
        min_sum_case1 = float('inf')
        if K_A > 0 or K_B > 0:
            if K_A == 0:
                B = (N + K_B - 1) // K_B
                min_sum_case1 = B
            elif K_B == 0:
                A = (N + K_A - 1) // K_A
                min_sum_case1 = A
            else:
                max_A = (N + K_A - 1) // K_A
                max_A = min(max_A, 10**6)
                for A in range(0, max_A + 1):
                    rem = N - A * K_A
                    if rem <= 0:
                        B = 0
                    else:
                        B = (rem + K_B - 1) // K_B
                    current_sum = A + B
                    if current_sum < min_sum_case1:
                        min_sum_case1 = current_sum
        ans = min(ans, min_sum_case1)
    
    # Case 3: Combination of K selections and rows/columns
    A_max = (H + L_A - 1) // L_A
    for A in range(0, A_max + 1):
        R = min(A * L_A, H)
        # Case 1: B*L_B <= W
        denominator = K_B + R * L_B
        B1 = None
        if denominator == 0:
            if K_B == 0 and R * L_B == 0:
                if A * K_A >= N:
                    B1 = 0
        else:
            numerator = N - A * K_A
            if numerator <= 0:
                B1 = 0
            else:
                B1 = (numerator + denominator - 1) // denominator
                B_max1 = W // L_B
                if B1 > B_max1:
                    B1 = None
        if B1 is not None:
            B1 = max(B1, 0)
            current_sum = A + B1
            ans = min(ans, current_sum)
        
        # Case 2: B*L_B >= W
        required = N - R * W - A * K_A
        B2 = None
        if K_B == 0:
            if required <= 0:
                B2 = (W + L_B - 1) // L_B
        else:
            if required <= 0:
                B2 = (W + L_B - 1) // L_B
            else:
                B_min_required = (required + K_B - 1) // K_B
                B_min_col = (W + L_B - 1) // L_B
                B2 = max(B_min_required, B_min_col)
        if B2 is not None:
            B2 = max(B2, 0)
            current_sum = A + B2
            ans = min(ans, current_sum)
    
    print(ans)

if __name__ == "__main__":
    main()
0