結果
問題 | No.3097 Azuki Kurai |
ユーザー |
![]() |
提出日時 | 2025-04-06 01:33:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,337 ms / 4,000 ms |
コード長 | 1,125 bytes |
コンパイル時間 | 531 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 79,820 KB |
最終ジャッジ日時 | 2025-04-06 01:33:43 |
合計ジャッジ時間 | 20,468 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
n,m,k = map(int,input().split()) a = list(map(int,input().split())) b = list(map(int,input().split())) mask=(1<<n)-1 p=mask+1 def next(f,g): ret = f for i in range(n): if (f&(1<<i)) > 0: if(g&(1<<i)) == 0: j=(i+1)%n ret |= (1<<j) j=(i+n-1)%n ret |= (1<<j) return ret def azuki_kurai(v,b): return v&(mask^(1<<b)) pc = [0]*p for i in range(p): v=i for j in range(n): if i&(1<<j): pc[i]+=1 isin =[[] for _ in range(p)] for i in range(p): for j in range(p): if i&j==j: isin[i].append(j) nxt =[[0]*p for _ in range(p)] for f in range(p): for g in isin[f]: nxt[f][g]=next(f,g) dp = [0]*p for i in range(p): dp[i]=0 for j in range(n): if i & (1<<j) ==0: dp[i]+=a[j] for _m in range(m): ndp=[10**18]*p _b=b[_m]-1 for f in range(p): for g in isin[f]: nv = azuki_kurai(nxt[f][g],_b) ndp[nv]=min(ndp[nv],dp[f]+k*pc[g]) #print(nv,f,g,ndp[nv],dp[f]) dp=ndp print(dp[0])