結果

問題 No.2869 yuusaan's Knapsacks
コンテスト
ユーザー PNJ
提出日時 2024-09-02 10:53:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,688 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 277,564 KB
最終ジャッジ日時 2024-09-02 10:53:46
合計ジャッジ時間 11,161 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 67280421310721
def popcount(n):
  c=(n&0x5555555555555555)+((n>>1)&0x5555555555555555)
  c=(c&0x3333333333333333)+((c>>2)&0x3333333333333333)
  c=(c&0x0f0f0f0f0f0f0f0f)+((c>>4)&0x0f0f0f0f0f0f0f0f)
  c=(c&0x00ff00ff00ff00ff)+((c>>8)&0x00ff00ff00ff00ff)
  c=(c&0x0000ffff0000ffff)+((c>>16)&0x0000ffff0000ffff)
  c=(c&0x00000000ffffffff)+((c>>32)&0x00000000ffffffff)
  return c

def ranked_zeta_transform(f):
  n = (len(f) - 1).bit_length()
  Rf = [[0 for _ in range(n + 1)] for _ in range(1 << n)]
  for s in range(1 << n):
    Rf[s][popcount(s)] = f[s]
  for i in range(n):
    w = 1 << i
    for p in range(0,1 << n,2 * w):
      for s in range(p,p + w):
        t = s | (1 << i)
        for d in range(n + 1):
          Rf[t][d] = (Rf[t][d] + Rf[s][d]) % mod
  return Rf

def ranked_mobius_transform(Rf):
  n = (len(Rf) - 1).bit_length()
  for i in range(n):
    w = 1 << i
    for p in range(0,1 << n,2 * w):
      for s in range(p,p + w):
        t = s | (1 << i)
        for d in range(n + 1):
          Rf[t][d] = (Rf[t][d] - Rf[s][d]) % mod
  f = [0 for _ in range(1 << n)]
  for s in range(1 << n):
    f[s] = Rf[s][popcount(s)]
  return f

def subset_convolution(A,B):
  RA = ranked_zeta_transform(A)
  RB = ranked_zeta_transform(B)
  n = (len(RA) - 1).bit_length()
  for s in range(1 << n):
    for d in range(n,-1,-1):
      x = 0
      for i in range(d + 1):
        x = (x + RA[s][i] * RB[s][d - i] % mod) % mod
      RA[s][d] = x
  C = ranked_mobius_transform(RA)
  for i in range(len(C)):
    if C[i] > 0:
      C[i] = 1
  return C

N,M = map(int,input().split())
E = list(map(int,input().split()))
V,W = [0] * M,[0] * M
for i in range(M):
  V[i],W[i] = map(int,input().split())

SW = [0 for _ in range(1 << M)]
SV = [0 for _ in range(1 << M)]
for s in range(1 << M):
  w,v = 0,0
  for j in range(M):
    if (s >> j) & 1:
      w += W[j]
      v += V[j]
  SW[s] = w
  SV[s] = v

dp = [[0 for s in range(1 << M)] for n in range(N)]
for n in range(N):
  if n == 0:
    for s in range(1 << M):
      if SW[s] <= E[n]:
        dp[n][s] = 1
    continue
  B = [0 for s in range(1 << M)]
  for s in range(1 << M):
    if SW[s] <= E[n]:
      B[s] = 1
  dp[n] = subset_convolution(dp[n - 1],B)

ans = 0
s = 0
for ss in range(1 << M):
  if dp[-1][ss]:
    if SV[ss] > ans:
      ans = SV[ss]
      s = ss

res = [0 for i in range(N)]
for n in range(N - 1,0,-1):
  for ss in range(1 << M):
    if (s & ss) != ss:
      continue
    if dp[n - 1][s ^ ss] & (SW[ss] <= E[n]):
      res[n] = ss
      s ^= ss
      break
res[0] = s

print(ans)
for n in range(N):
  X = []
  X.append(popcount(res[n]))
  for j in range(M):
    if (res[n] >> j) & 1:
      X.append(j + 1)
  print(*X)
0