結果
問題 | No.3097 Azuki Kurai |
ユーザー |
|
提出日時 | 2025-04-05 02:23:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,822 ms / 4,000 ms |
コード長 | 1,367 bytes |
コンパイル時間 | 535 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 87,992 KB |
最終ジャッジ日時 | 2025-04-05 14:11:03 |
合計ジャッジ時間 | 34,818 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
def popcount(n): ret=0 for i in range(65): if n&(1<<i): ret+=1 return ret N,M,K=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) INF=10**18 dp=[[INF]*(1<<N) for i in range(M+1)] for i in range(1<<N): dp[0][i]=0 for j in range(N): if (i&(1<<j)==0): dp[0][i]+=A[j] pl=[[] for i in range(1<<N)] mae=[[[] for _ in range(1<<N)] for _ in range(N)] for i in range(1<<N): c=i while True: pl[i].append((popcount(i)-popcount(c))*K) if c==0: break c=(c-1)&i for p in range(N): for i in range(1<<N): c=i while True: now=i now |= ((c * 2) - ((c * 2) & (1 << N))) now |= (((c * 2) & (1 << N)) >> N) now |= (c // 2) now |= (c % 2) * (1 << (N - 1)) now -= (now & (1 << p)) mae[p][i].append(now) if c==0: break c=(c-1)&i for p in range(M): b=B[p]-1 for i in range(1<<N): F=0 c=i while True: dp[p+1][mae[b][i][F]]=min(dp[p+1][mae[b][i][F]],dp[p][i]+pl[i][F]) F+=1 if (c==0): break c=(c-1)&i for i in range(M): print(dp[i+1][0])