結果

問題 No.1872 Dictionary Order
ユーザー lam6er
提出日時 2025-03-20 21:19:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 208 ms / 2,000 ms
コード長 1,690 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 108,844 KB
最終ジャッジ日時 2025-03-20 21:20:16
合計ジャッジ時間 4,587 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))

# Shift to 1-based indexing for easier handling
A = [0] + A  # A[1..n]
P = [0] + P  # P[1..n]

# Initialize DP table
dp = [[False] * (m + 1) for _ in range(n + 2)]
# Base case: after the last element (n+1), sum 0 is possible
dp[n+1][0] = True

for i in range(n, 0, -1):
    for s in range(m + 1):
        # Option 1: do not take i
        option_not_take = dp[i+1][s]
        # Option 2: take i, if possible
        option_take = False
        if s >= A[i] and dp[i+1][s - A[i]]:
            option_take = True
        dp[i][s] = option_not_take or option_take

path = []
prev_j = 0
remaining_sum = m
possible = True

while remaining_sum > 0:
    eligible = []
    for j in range(prev_j + 1, n+1):
        if A[j] > remaining_sum:
            continue
        required = remaining_sum - A[j]
        next_i = j + 1
        if next_i > n:
            # Check if required is 0
            if required == 0:
                eligible.append(j)
        else:
            if dp[next_i][required]:
                eligible.append(j)
    if not eligible:
        possible = False
        break
    # Find the eligible j with minimal P[j], and smallest index in case of tie
    min_p = float('inf')
    best_j = -1
    for j in eligible:
        if P[j] < min_p or (P[j] == min_p and j < best_j):
            min_p = P[j]
            best_j = j
    if best_j == -1:
        possible = False
        break
    path.append(best_j)
    remaining_sum -= A[best_j]
    prev_j = best_j

if possible and remaining_sum == 0:
    print(len(path))
    print(' '.join(map(str, path)))
else:
    print(-1)
0