Submission #3609081
Source Code Expand
H,W,K=map(int,input().split()) C=[1,1,2,3,5,8,13,21] Amida=[[0]*W for h in range(H+1)] for h in range(H+1): if W==1: break for w in range(W): if h==0: if w==0: Amida[h][w]=1 else: Amida[h][w]=0 elif w==0: Amida[h][w]=C[W-2]*Amida[h-1][w+1]+C[W-1]*Amida[h-1][w] elif w==W-1: Amida[h][w]=C[W-2]*Amida[h-1][w-1]+C[W-1]*Amida[h-1][w] else: Amida[h][w]+=(C[w-1]*C[W-w-1]*Amida[h-1][w-1]) Amida[h][w]+=(C[w]*C[W-w-1]*Amida[h-1][w]) Amida[h][w]+=C[w]*C[W-w-2]*Amida[h-1][w+1] Amida[h][w]=Amida[h][w]%1000000007 if W==1: if K==1: print(1) else: print(0) else: print(Amida[H][K-1])
Submission Info
Submission Time | |
---|---|
Task | D - Number of Amidakuji |
User | guest_C |
Language | Python (3.4.3) |
Score | 400 |
Code Size | 701 Byte |
Status | AC |
Exec Time | 19 ms |
Memory | 3064 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt |
All | in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in01.txt | AC | 18 ms | 3064 KB |
in02.txt | AC | 19 ms | 3064 KB |
in03.txt | AC | 19 ms | 3064 KB |
in04.txt | AC | 18 ms | 3064 KB |
in05.txt | AC | 18 ms | 3064 KB |
in06.txt | AC | 18 ms | 3064 KB |
in07.txt | AC | 17 ms | 3064 KB |
in08.txt | AC | 18 ms | 3064 KB |
in09.txt | AC | 18 ms | 3064 KB |
in10.txt | AC | 18 ms | 3064 KB |
sample_01.txt | AC | 17 ms | 3064 KB |
sample_02.txt | AC | 17 ms | 3064 KB |
sample_03.txt | AC | 17 ms | 3064 KB |
sample_04.txt | AC | 17 ms | 3064 KB |
sample_05.txt | AC | 17 ms | 3064 KB |
sample_06.txt | AC | 18 ms | 3064 KB |