結果
問題 |
No.332 数列をプレゼントに
|
ユーザー |
![]() |
提出日時 | 2023-12-01 05:02:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 1,865 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 76,988 KB |
最終ジャッジ日時 | 2024-09-26 15:09:06 |
合計ジャッジ時間 | 5,610 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
import sys readline=sys.stdin.readline def Hirschberg_Algorithm(N,lst,S,bit_set=False): partial_sum=[0]*(N+1) partial_sum[0]=0 partial_sum[N]=S stack=[(0,N)] while stack: l,r=stack.pop() mid=(l+r)//2 s=partial_sum[r]-partial_sum[l] if bit_set: dpL=Bit_Set(1,element_range=s+1) else: dpL=1 for i in range(l,mid): dpL|=dpL<<lst[i] if not bit_set: dpL&=(1<<s+1)-1 if bit_set: dpR=Bit_Set(1<<s,element_range=s+1) else: dpR=1<<s for i in range(mid,r): dpR|=dpR>>lst[i] dp=dpL&dpR if bit_set and not dp.bit_set or not bit_set and dp==0: return None partial_sum[mid]=partial_sum[l]+(dp.Find_First() if bit_set else (dp&-dp).bit_length()-1) if mid-l>=2: stack.append((l,mid)) if r-mid>=2: stack.append((mid,r)) return partial_sum N,X=map(int,readline().split()) A=list(map(int,readline().split())) M=10**5 idx0=[] idx1=[] s1=0 for i in range(N): if A[i]>=M: idx0.append(i) else: idx1.append(i) s1+=A[i] le0=len(idx0) le1=len(idx1) dp=1 for i in range(1,le1+1): dp|=dp<<A[idx1[i-1]] for bit in range(1<<le0): s=sum(A[idx0[i]] for i in range(le0) if bit&1<<i) if s1>=X-s>=0 and dp&1<<X-s: ans_lst=[None]*N for i in range(le0): if bit&1<<i: ans_lst[idx0[i]]="o" else: ans_lst[idx0[i]]="x" cumsum_A=Hirschberg_Algorithm(le1,[A[i] for i in idx1],X-s) for i in range(le1): if cumsum_A[i]<cumsum_A[i+1]: ans_lst[idx1[i]]="o" else: ans_lst[idx1[i]]="x" print(*ans_lst,sep="") break else: print("No")