結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
![]() |
提出日時 | 2023-06-15 12:54:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 516 ms / 3,000 ms |
コード長 | 736 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 81,356 KB |
最終ジャッジ日時 | 2024-06-23 13:34:18 |
合計ジャッジ時間 | 12,220 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
import collections N = int(input()) A = list(map(int,input().split())) ZERO = A.count(0) ONE = A.count(1) L = [] SEP = [] for a in A: if a==2: if len(SEP)>0: L.append(SEP) SEP = [] else: SEP.append(a) L.append(SEP) #コストを設定 DP = collections.defaultdict(lambda:10**4) DP[(0,0)]=0 for l in L: NDP = collections.defaultdict(lambda:10**4) CA = collections.Counter(l) for k,v in DP.items(): z,o = k if z+len(l)<=ZERO: NDP[(z+len(l),o)]=min(NDP[(z+len(l),o)],v+CA[1]) if o+len(l)<=ONE: NDP[(z,o+len(l))]=min(NDP[(z,o+len(l))],v+CA[0]) DP = NDP if DP[(ZERO,ONE)]==10**4: print(-1) else: print(DP[(ZERO,ONE)]//2)