Contest Duration: ~ (local time) (300 minutes) Back to Home

Submission #17505441

Source Code Expand

Copy
```import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def INP():
N=10;A=10
n=random.randint(1,N)
a=[random.randint(1,A) for i in range(n)]
return n,a
def Rtest(T):
case,err=0,0
for i in range(T):
inp=INP()
a1=naive(*inp)
a2=solve(*inp)
if a1!=a2:
print((a1,a2),inp)
err+=1
case+=1
print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
org_inp=[];g=[[] for i in range(V)]
FromStdin=True if ls==None else False
for i in range(E):
if FromStdin:
inp=LI()
org_inp.append(inp)
else:
inp=ls[i]
if len(inp)==2:
a,b=inp;c=1
else:
a,b,c=inp
if index==1:a-=1;b-=1
aa=(a,c);bb=(b,c);g[a].append(bb)
if not Directed:g[b].append(aa)
return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
mp=[boundary]*(w+2);found={}
for i in R(h):
s=input()
for char in search:
if char in s:
found[char]=((i+1)*(w+2)+s.index(char)+1)
mp_def[char]=mp_def[replacement_of_found]
mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
mp+=[boundary]*(w+2)
return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
rt=[0]
for i in ls:rt+=[rt[-1]+i]
return rt
def bit_combination(n,base=2):
rt=[]
for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
return rt
def gcd(x,y):
if y==0:return x
if x%y==0:return y
while x%y!=0:x,y=y,x%y
return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)

show_flg=False
show_flg=True

ans=0

n,k=LI()
dp=[0]*(n+1) # dp[i] number of case where last not stop at station i
dp=[0]*(n+1) # dp[i] number of case where stopped at last i statsions
dp[0]=1

dp=deque([0,1])
#dp[i+1]+=dp[i]
#dp[0]=sum(dp[1]...dp[k-1])
#nx=sum(dp[0],dp[1]...dp[k-1]),dp[0],dp[1],...,dp[k-2]

a=1
t=' '
for i in range(n-1):
if i>=k-1:
a-=dp[-1]
dp.pop()
dp.appendleft(a%mo)
a+=dp[0]
#    show(i,t,dp,a)

ans=sum(list(dp)[1:k])
print(ans%mo)

```

#### Submission Info

Submission Time 2020-10-18 20:23:32+0900 F - 準急 keroru PyPy3 (7.3.0) 4 3916 Byte AC 223 ms 118584 KB

#### Judge Result

Set Name All
Score / Max Score 4 / 4
Status
 AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 223 ms 93544 KB
01 182 ms 118584 KB
02 147 ms 85984 KB
03 139 ms 83572 KB
04 150 ms 92588 KB
90 116 ms 78028 KB
91 117 ms 77872 KB