結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
|
提出日時 | 2022-09-21 16:15:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 487 ms / 3,000 ms |
コード長 | 744 bytes |
コンパイル時間 | 554 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 314,752 KB |
最終ジャッジ日時 | 2024-12-22 04:10:38 |
合計ジャッジ時間 | 10,584 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
n=int(input()) a=list(map(int, input().split())) b=[] L=0 O=0 alllen=0 allone=0 for i in range(n): if a[i]==2: if L>0: b.append([L, O]) L=0 O=0 else: alllen+=1 L+=1 if a[i]==1: allone+=1 O+=1 if L>0: b.append([L, O]) m=len(b) o=n*2+10 dp=[[1e9]*(o) for _ in range(m+1)] dp[0][n]=0 for i in range(m): len, one = b[i] zero = len - one for j in range(o): if dp[i][j]==1e9: continue if j + one < o: dp[i+1][j+one]=min(dp[i+1][j+one],dp[i][j]+one) if j - zero >= 0: dp[i+1][j-zero]=min(dp[i+1][j-zero],dp[i][j]) if dp[m][n] == 1e9: print(-1) else: print(dp[m][n])