Submission #46169169

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict
def ope_number_digit(N,K,P):
    # 整数Nの左からK桁目をPに書き換える
    N -= get_number_digit(N,K) * pow(10,K-1)
    N += P * pow(10,K-1)
    return N
def get_number_digit(N,K):
    # 整数Nの左からK桁目を得る
    return N // pow(10,K-1) - N // pow(10,K) * 10
N,K,P = map(int, input().split())
C_list = list()
A_list = list()
for i in range(N):
    line = [int(e) for e in input().split()]
    C = line[0]
    A = line[1:]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import defaultdict

def ope_number_digit(N,K,P):
    # 整数Nの左からK桁目をPに書き換える
    N -= get_number_digit(N,K) * pow(10,K-1)
    N += P * pow(10,K-1)
    return N

def get_number_digit(N,K):
    # 整数Nの左からK桁目を得る
    return N // pow(10,K-1) - N // pow(10,K) * 10

N,K,P = map(int, input().split())

C_list = list()
A_list = list()

for i in range(N):
    line = [int(e) for e in input().split()]
    C = line[0]
    A = line[1:]
    C_list.append(C)
    A_list.append(A[::-1])

dp = defaultdict(int)
dp[0] = 0
valid_keys = {0}

for i in range(N):
    C = C_list[i]
    A = A_list[i]

    new_keys = set()
    new_val = defaultdict(int)  # 複数回使用とならないように更新値の一時置きするdict

    for key in valid_keys:
        # 当該開発案を実行したときのパラメータパターンを算出
        parameter = key

        for j in range(K):
            digit_j = get_number_digit(parameter,K-j)
            
            if digit_j + A[j] >= P:
                parameter = ope_number_digit(parameter,K-j,P)
            else:
                parameter = ope_number_digit(parameter,K-j,digit_j + A[j])

        # 新規のパラメータパターンなら探索候補に追加するために確保
        if parameter not in valid_keys:
            new_keys.add(parameter)

        # 当該パラメータパターンの最安コストを更新
        if new_val[parameter] == 0:
            new_val[parameter] = C + dp[key]
        else:
            new_val[parameter] = min(C + dp[key],new_val[parameter])
    
    new_val[0] = 0

    # 確保した新規のパラメータパターンを探索候補に追加
    valid_keys |= new_keys
    # 更新値を反映する
    for k,v in new_val.items():
        if dp[k] == 0:
            dp[k] = v
        else:    
            dp[k] = min(dp[k],v)

key = 0
for i in range(K):
    key *= 10
    key += P

if dp[key] == 0:
    print(-1)
else:
    print(dp[key])

Submission Info

Judge Result