結果
問題 | No.1701 half price |
ユーザー |
![]() |
提出日時 | 2021-02-21 22:46:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,769 ms / 3,000 ms |
コード長 | 1,901 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 76,320 KB |
最終ジャッジ日時 | 2024-07-23 03:25:48 |
合計ジャッジ時間 | 6,035 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
class INPUT:def __init__(self):from sys import argvif argv[-1] in ["./Main.py","prog.py","Main.py"]:#Atcoder:./Main.py,Wandbox:prog.py,yukicoder:Main.pyself.l=open(0).read().split()[::-1]else:self.l=open("_input.txt",mode="r").read().split()[::-1]self.length=len(self.l)returndef stream(self,k=1,f=int,f2=False):assert(-1<k)m=self.lengthif m==0 or m<k:raise Exception("There is no input!")elif f!=str:if k==0:self.length=0return list(map(f,self.l[::-1]))if k==1 and not f2:self.length-=1return f(self.l.pop())if k==1 and f2:self.length-=1return [f(self.l.pop())]ret=[]for _ in [0]*k:ret.append(f(self.l.pop()))self.length-=kreturn retelse:if k==0:self.length=0return self.l[::-1]if k==1 and not f2:self.length-=1return self.l.pop()if k==1 and f2:self.length-=1return [self.l.pop()]ret=[]for _ in [0]*k:ret.append(self.l.pop())self.length-=kreturn retpin=INPUT().streamdef change(n,k):ret=""while n!=0:ret+=str(n%k)n//=kreturn retdef main():N,W=pin(2)assert(1<=N<=13)assert(0<=W<=pow(10,9))a=pin(0)for i in a:assert(0<=i<=pow(10,9))debug=i%2assert(debug==0)cnt_0=a.count(0)n=N-cnt_0A=list(filter(lambda x:x!=0,a))if W==0:return print(pow(2,cnt_0)-1)#何も選ばないことはできないans=set()B=[i//2 for i in A]for i in range(3**n):s=0b=""u=change(i,3).ljust(N,"0")for j in range(n):if u[j]=="1":s+=A[j]b+="1"elif u[j]=="2":s+=B[j]b+="1"else:b+="0"if s==W:ans.add(b)print(len(ans)*pow(2,cnt_0))returnmain()