結果
問題 |
No.2708 Jewel holder
|
ユーザー |
|
提出日時 | 2024-04-18 09:27:45 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 656 bytes |
コンパイル時間 | 352 ms |
コンパイル使用メモリ | 82,124 KB |
実行使用メモリ | 70,152 KB |
最終ジャッジ日時 | 2024-10-10 02:43:28 |
合計ジャッジ時間 | 2,273 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 5 |
ソースコード
H, W=map(int, input().split()) S=list(input() for i in range(H)) # dp[h][w][n] で h行w列で宝石をn個持っている場合の数 dp=[[[0 for k in range(109)] for j in range(W)] for i in range(H)] dp[0][0][1]=1 ans=0 for h in range(H): for w in range(W): for n in range(109): for dh, dw in ((1,0),(0,1)): nh, nw=h+dh, w+dw if (nh<H and nw<W)==False: continue if S[nh][nw]=="o" and n+1<len(dp[nh][nw]): dp[nh][nw][n+1]+=dp[h][w][n] elif S[nh][nw]=="x": if n-1>=0: dp[nh][nw][n-1]+=dp[h][w][n] for n in range(1, len(dp[0][0])): ans+=dp[H-1][W-1][n] print(ans) # print(dp)