結果

問題 No.467 隠されていたゲーム
ユーザー lam6er
提出日時 2025-04-16 00:28:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,432 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 53,496 KB
最終ジャッジ日時 2025-04-16 00:30:21
合計ジャッジ時間 4,067 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 1 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    n = int(sys.stdin.readline())
    d = list(map(int, sys.stdin.readline().split()))
    x, y = map(int, sys.stdin.readline().split())
    x_abs = abs(x)
    y_abs = abs(y)
    D = max(x_abs, y_abs)
    if D == 0:
        print(0)
        return
    d.sort()
    max_d = d[-1]
    if max_d == 0:
        print(-1)
        return
    k_min = (D + max_d - 1) // max_d  # ceil(D / max_d)
    target_parity = D % 2

    # Check for k_min, k_min+1, k_min+2
    for k_candidate in [k_min, k_min + 1, k_min + 2]:
        # Initialize DP: dp[parity] = maximum sum achievable with that parity
        dp = [-1] * 2
        dp[0] = 0  # Starting with 0 steps, sum 0 (parity 0)
        for step in range(k_candidate):
            new_dp = [-1] * 2
            for parity in [0, 1]:
                if dp[parity] == -1:
                    continue
                for di in d:
                    new_sum = dp[parity] + di
                    new_parity = new_sum % 2
                    if new_sum > new_dp[new_parity]:
                        new_dp[new_parity] = new_sum
            dp = new_dp
            if dp[0] == -1 and dp[1] == -1:
                # No way to proceed further
                break
        # Check if target parity is achievable and sum >= D
        if dp[target_parity] >= D:
            print(k_candidate)
            return
    print(-1)

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