結果
問題 |
No.1872 Dictionary Order
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:53:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 1,690 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 108,376 KB |
最終ジャッジ日時 | 2025-03-20 18:54:34 |
合計ジャッジ時間 | 4,990 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
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)