結果
問題 | No.2056 非力なレッド |
ユーザー |
![]() |
提出日時 | 2022-08-22 01:36:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 1,123 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 157,732 KB |
最終ジャッジ日時 | 2024-10-10 06:30:43 |
合計ジャッジ時間 | 10,684 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
from random import randrange as rddef make(N,X,M,A):n=rd(1,N+1)x=rd(1,X+1)m=rd(M+1)a=[rd(1,A+1) for i in range(n)]return n,x,m,adef sol1(n,x,m,A):a=A[:]need=[0]*(n+1)for i in range(n):while a[i]>=x:need[i]+=1a[i]//=2for i in range(n-1,-1,-1):need[i]=max(need[i],need[i+1])if sum(need)<=m:return "Yes"return "No"def sol2(n,x,m,A):a=[0]+A[:]dp=[[10**10]*33 for i in range(n+3)]dp[0][32]=0for i in range(1,n+1):sdp=[10**10]*35for j in range(32,-1,-1):sdp[j]=min(sdp[j+1],dp[i-1][j])for j in range(33):if x<=a[i]//(2**j):continuedp[i][j]=sdp[j]+jres=10**10for j in range(33):res=min(res,dp[n][j])if res<=m:return "Yes"return "No"n,x,m=map(int,input().split())a=list(map(int,input().split()))print(sol2(n,x,m,a))cnt=0while 0:cnt+=1print(cnt)n,x,m,a=make(15,30,30,60)ans1=sol1(n,x,m,a)ans2=sol2(n,x,m,a)if ans1!=ans2:print("!")exit()print(ans1)