結果

問題 No.3219 Ruler to Maximize
コンテスト
ユーザー ああ
提出日時 2025-08-10 02:29:30
言語 Python3
(3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 65 ms / 2,000 ms
+ 594µs
コード長 751 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 56 ms
コンパイル使用メモリ 14,848 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2026-11-12 03:09:13
合計ジャッジ時間 3,712 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

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