結果
問題 | No.1606 Stuffed Animals Keeper |
ユーザー |
👑 ![]() |
提出日時 | 2021-07-16 22:38:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 101 ms / 3,000 ms |
コード長 | 729 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 71,040 KB |
最終ジャッジ日時 | 2024-07-06 10:07:59 |
合計ジャッジ時間 | 4,142 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#================================================= N=int(input()) A=list(map(int,input().split()))+[2] #=== P=A.count(0) Q=A.count(1) #=== 可能どうかの判定 X=[] x=0 for a in A: if a!=2: x+=1 else: if x: X.append(x) x=0 DP=[0]*(P+1); DP[0]=1 for x in X: for k in range(P,x-1,-1): DP[k]|=DP[k-x] if DP[P]==0: exit(print(-1)) #=== 回数を求める Y=[] p=q=0 p_sum=0 for a in A: if a==0: p+=1 p_sum+=1 elif a==1: q+=1 else: Y.append((p,q)) p=q=0 inf=float("inf") DP=[inf]*(p_sum+1); DP[0]=0 for p,q in Y: r=p+q for k in range(p_sum,r-1,-1): DP[k]=min(DP[k],DP[k-r]+q) print(DP[p_sum])