結果
問題 |
No.1929 Exponential Sequence
|
ユーザー |
|
提出日時 | 2022-05-07 10:39:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 767 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 81,988 KB |
実行使用メモリ | 86,236 KB |
最終ジャッジ日時 | 2024-09-14 03:55:00 |
合計ジャッジ時間 | 2,646 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
n,S = map(int,input().split()) A = list(map(int,input().split())) A1 = A[:n//2] A2 = A[n//2:] def makeaccum(A,S): dicA = {} dicA[0] = 1 for a in A: ndicA = {} for k,v in dicA.items(): now = a for j in range(1,30): if k+now <= S: ndicA[k+now] = ndicA.get(k+now,0)+v now *= a dicA = ndicA s = sorted(set(dicA.keys())) accum = [0]+[dicA[i] for i in s] return accum,s accum1,s1 = makeaccum(A1,S) accum2,s2 = makeaccum(A2,S) for i in range(len(accum2)-1): accum2[i+1] += accum2[i] ans = 0 now = 0 l = len(s2) for a,s in zip(accum1[1:][::-1],s1[::-1]): while now < l and s+s2[now] <= S: now += 1 ans += a*accum2[now] print(ans)