結果
問題 | No.1694 ZerOne |
ユーザー |
![]() |
提出日時 | 2021-10-01 22:18:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 373 ms / 2,000 ms |
コード長 | 1,506 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 101,008 KB |
最終ジャッジ日時 | 2024-07-19 11:48:02 |
合計ジャッジ時間 | 8,225 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
from collections import defaultdict, deque, Counter from heapq import heappush, heappop, heapify from copy import deepcopy import bisect import random from itertools import permutations, accumulate, combinations, product import sys import string from bisect import bisect_left, bisect_right from math import factorial, ceil, floor from operator import mul from functools import reduce from pprint import pprint from copy import deepcopy from math import gcd, log2,atan2,atan,sin,cos,pi import functools import typing def LI(): return list(map(int, sys.stdin.readline().split())) def I(): return int(sys.stdin.readline()) def LS(): return sys.stdin.readline().split() def S(): return sys.stdin.readline().strip() def IR(n): return [I() for i in range(n)] def LIR(n): return [LI() for i in range(n)] def SR(n): return [S() for i in range(n)] def LSR(n): return [LS() for i in range(n)] def SRL(n): return [list(S()) for i in range(n)] def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)] mod=10**9+7 INF=10**30 s=S() n=len(s) idx_list=[] c=s.count("1") for d in range(n): if s[d]=="1": idx_list+=[d] dp=[[defaultdict(int) for _ in range(n)] for _ in range(c+1)] dp[0][0][0]=1 for i in range(c): idx=idx_list[i] for pre in range(n): dd=dp[i][pre] for j in range(pre+1 if i else 0,n): diff=idx-j for k,v in dd.items(): dp[i+1][j][k+diff]+=v ans=0 for f in range(n): ans+=dp[c][f][0] print(ans)