結果

問題 No.2227 King Kraken's Attack
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:01:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,572 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 74,996 KB
最終ジャッジ日時 2025-04-15 23:02:37
合計ジャッジ時間 4,160 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    H, W, L_A, L_B, K_A, K_B = map(int, input().split())
    
    min_sum = float('inf')
    
    # Candidate 1: Cover all rows and columns with initial parts
    sum_ceil = (H + L_A - 1) // L_A + (W + L_B - 1) // L_B
    min_sum = min(min_sum, sum_ceil)
    
    # Candidate 2: Cover all cells with K parts
    if K_A + K_B > 0:
        total = H * W
        sum_k = (total + (K_A + K_B) - 1) // (K_A + K_B)
        min_sum = min(min_sum, sum_k)
    else:
        if H == 0 or W == 0:
            min_sum = 0
    
    # Iterate over possible A values
    max_A = min((H + L_A - 1) // L_A + 100, 10**6)
    for A in range(0, max_A + 1):
        rows_covered = A * L_A
        if rows_covered > H:
            X = 0
        else:
            X = (H - rows_covered) * W
        
        # Scenario 1: B >= ceil(W / L_B)
        B_ceil_vertical = (W + L_B - 1) // L_B
        required_K_scenario1 = X
        
        scenario1_possible = True
        if K_B == 0:
            if A * K_A >= required_K_scenario1:
                B_scenario1 = B_ceil_vertical
            else:
                scenario1_possible = False
        else:
            numerator = max(required_K_scenario1 - A * K_A, 0)
            B_min_scenario1 = (numerator + K_B - 1) // K_B
            B_scenario1 = max(B_ceil_vertical, B_min_scenario1)
        
        if scenario1_possible:
            sum_scenario1 = A + B_scenario1
            if A * K_A + B_scenario1 * K_B >= required_K_scenario1:
                min_sum = min(min_sum, sum_scenario1)
        
        # Scenario 2: B < ceil(W / L_B)
        B_max_scenario2 = B_ceil_vertical - 1
        if B_max_scenario2 < 0:
            continue
        
        required_K_scenario2 = X
        
        # Calculate B_min for scenario2
        B_min_scenario2 = 0
        if K_B == 0 and K_A == 0:
            if required_K_scenario2 == 0 and (W * H) == 0:
                B_min_scenario2 = 0
            else:
                continue
        else:
            # Compute B_min for (W - B*L_B)*H <= A*K_A + B*K_B
            # => B*(K_B + L_B * H) >= W*H - A*K_A
            numerator = W * H - A * K_A
            denominator = K_B + L_B * H
            if denominator == 0:
                if numerator <= 0:
                    B_min_equation = 0
                else:
                    continue
            else:
                if numerator <= 0:
                    B_min_equation = 0
                else:
                    B_min_equation = (numerator + denominator - 1) // denominator
            
            # Compute B_min for required_K_scenario2
            if K_B == 0:
                if A * K_A >= required_K_scenario2:
                    B_min_x = 0
                else:
                    continue
            else:
                B_min_x = max(0, (required_K_scenario2 - A * K_A + K_B - 1) // K_B)
            
            B_min_scenario2 = max(B_min_equation, B_min_x)
        
        if B_min_scenario2 > B_max_scenario2:
            continue
        
        sum_scenario2 = A + B_min_scenario2
        if A * K_A + B_min_scenario2 * K_B >= required_K_scenario2:
            # Check vertical coverage
            columns_covered = B_min_scenario2 * L_B
            if columns_covered >= W:
                pass
            else:
                required_Y = (W - columns_covered) * H
                if A * K_A + B_min_scenario2 * K_B < required_Y:
                    continue
            min_sum = min(min_sum, sum_scenario2)
    
    print(min_sum)

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