結果

問題 No.3219 Ruler to Maximize
ユーザー ああ
提出日時 2025-08-10 02:29:30
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 100 ms / 2,000 ms
コード長 751 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 13,696 KB
最終ジャッジ日時 2025-08-10 02:29:35
合計ジャッジ時間 4,174 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #

n=int(input())
a=list(map(int,input().split()))
v=4096
dp=[[-1]*v for i in range(n+1)]
dp[0][0]=0
for i in range(n):
	for j in range(v):
		if dp[i][j]<0:
			continue
		if (j|a[i])&dp[i][j]==0:
			dp[i+1][j|a[i]]=max(dp[i][j],dp[i+1][j|a[i]])
		if (dp[i][j]|a[i])&j==0:
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]|a[i])
ans=0
for i in range(v):
	ans=max(ans,dp[n][i]*i)
if ans==0:
	print(ans)
	print("B"*n)
else:
	b=[]
	q,w=0,0
	for i in range(v):
		if dp[n][i]*i==ans:
			q=i;w=dp[n][i]
			break
	for i in range(n,0,-1):
		s=a[i-1]
		if dp[i-1][q]|s==w:
			b.append("W")
			w=dp[i-1][q]
			continue
		b.append("B")
		for j in range(q,-1,-1):
			if dp[i-1][j]<0:
				continue
			if dp[i-1][j]==w:
				q=j
				break
	b.reverse()
	print(ans)
	print("".join(b))
0