結果

問題 No.2025 Select $k$-th Submultiset
ユーザー qwewe
提出日時 2025-05-14 13:25:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,896 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 82,560 KB
最終ジャッジ日時 2025-05-14 13:26:47
合計ジャッジ時間 4,577 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N, L = map(int, sys.stdin.readline().split())
    # counts_orig for 1-indexed numbers, counts for 0-indexed numbers
    counts_orig = list(map(int, sys.stdin.readline().split())) 
    Q_count = int(sys.stdin.readline())
    
    # CAP for DP values, slightly larger than max k_i (10^18)
    CAP = 2 * (10**18) + 7 

    # dp[i][j] = number of ways to choose j items using numbers from index i to N-1 (0-indexed)
    # dp table dimensions: (N+1) x (L+1)
    # dp[N][0] = 1 (one way to choose 0 items from no numbers left: empty set)
    # dp[N][j > 0] = 0
    
    dp = [[0] * (L + 1) for _ in range(N + 1)]
    dp[N][0] = 1

    # Fill DP table
    # Iterate backwards for number index: from N-1 down to 0
    for i in range(N - 1, -1, -1):
        dp[i][0] = 1 # One way to choose 0 items (choose none of number i, and 0 from rest)
        
        c_current_num = counts_orig[i] # Count for number i (0-indexed)
        
        for j in range(1, L + 1):
            val = dp[i][j-1] + dp[i+1][j]
            # Cap before subtraction to prevent issues, though Python handles large integers.
            # Capping is mainly for limiting the magnitude.
            if val >= CAP: 
                val = CAP

            if j - 1 - c_current_num >= 0:
                val -= dp[i+1][j - 1 - c_current_num]
            
            # Ensure non-negative, then cap
            if val < 0:
                val = 0
            if val > CAP:
                val = CAP
            dp[i][j] = val
            
    output_lines = []
    for _ in range(Q_count):
        k = int(sys.stdin.readline())

        if k == 0 or k > dp[0][L]: # k is 1-indexed rank
            output_lines.append("-1")
            continue

        ans_counts = [0] * N
        current_L_remaining = L
        
        possible_to_form = True # Flag to track if k-th is found

        for i in range(N): # For number i (0-indexed, actual number i+1)
            found_count_for_this_num = False
            # Iterate count_val for number i from max possible down to 0
            # max_can_take = min(current_L_remaining, counts_orig[i])
            for count_val_for_num_i in range(min(current_L_remaining, counts_orig[i]), -1, -1):
                
                # Length to be formed by subsequent numbers
                rem_len_after_this_num = current_L_remaining - count_val_for_num_i
                
                # This check should not be strictly necessary due to loop bounds, but good for safety
                if rem_len_after_this_num < 0:
                     num_combinations = 0
                elif i == N - 1: # This is the last number (N-1 in 0-indexed)
                    if rem_len_after_this_num == 0: # Must fill exactly
                        num_combinations = 1
                    else:
                        num_combinations = 0
                else:
                    # Ways to form remaining length with numbers i+1 to N-1
                    num_combinations = dp[i + 1][rem_len_after_this_num]

                if k <= num_combinations:
                    ans_counts[i] = count_val_for_num_i
                    current_L_remaining -= count_val_for_num_i
                    found_count_for_this_num = True
                    break 
                else:
                    k -= num_combinations
            
            if not found_count_for_this_num:
                # This implies k was too large for any valid assignment for this num_i and subsequent ones
                possible_to_form = False
                break
        
        if possible_to_form and current_L_remaining == 0:
            output_lines.append(" ".join(map(str, ans_counts)))
        else:
            # This branch might be hit if found_count_for_this_num becomes false
            output_lines.append("-1") 

    sys.stdout.write("\n".join(output_lines) + "\n")

solve()
0