Submission #6208405

---

Source Code Expand

import numpy as np
N,M,Y,Z = map(int,input().split())
CP = [input().split() for _ in range(M)]
color, pts = zip(*CP)
pts = [int(x) for x in pts]
c_to_i = {x:i for i,x in enumerate(color)}
B = input()

# (最後に積んだブロック、コンプリートしたsubset) -> score
INF = 10**15
dp = np.full((M, 1<<M), -INF, dtype = np.int64)

subsets = np.arange(1<<M)

def update_dp(c):
  i = c_to_i[c]
  p = pts[i]
  bit = 1 << i
  contain = np.bitwise_and(bit,subsets).astype(np.bool)
  # 同色
  x = dp[i][contain] + max(0, p + Y)
  # 他の色から来る
  other = np.full(1<<M, -INF, dtype=np.int64)
  for j in range(M):
    if i == j:
      continue
    np.maximum(other, dp[j], out = other)
  y = np.maximum(other[contain], other[np.bitwise_xor(subsets[contain],bit)]) + p
  dp[i][contain] = np.maximum(dp[i][contain], np.maximum(x,y))
  # はじめて
  dp[i][bit] = np.maximum(dp[i][bit], p)

for b in B:
  update_dp(b)

dp = dp.max(axis = 0)
dp[-1] += Z # perfect
answer = dp.max()
# ひとつも積まない
if answer < 0:
  answer = 0
print(answer)

Submission Info

Judge Result