結果

問題 No.2003 Frog on Grid
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:23:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,368 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 109,584 KB
最終ジャッジ日時 2025-06-12 19:23:15
合計ジャッジ時間 6,193 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

H, W, K = map(int, input().split())
grid = [input().strip() for _ in range(H)]

# Initialize DP and prefix sums
dp = [[0] * (W + 1) for _ in range(H + 1)]
row_prefix = [[0] * (W + 1) for _ in range(H + 1)]
prefix = [[0] * (W + 1) for _ in range(H + 1)]

# Base case: starting cell (1,1)
if grid[0][0] == '.':
    dp[1][1] = 1
    row_prefix[1][1] = 1
    prefix[1][1] = 1

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if i == 1 and j == 1:
            continue  # already initialized
        if grid[i-1][j-1] == '#':
            dp[i][j] = 0
        else:
            S = i + j - K
            T = S - 1
            # Calculate sum_rect using prefix sums
            sum_rect = (prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]) % MOD
            sum_lower = 0
            # Iterate over x from 1 to i
            for x in range(1, i + 1):
                y_max = T - x
                if y_max < 1:
                    continue
                if y_max > j:
                    y_max = j
                sum_lower = (sum_lower + row_prefix[x][y_max]) % MOD
            dp[i][j] = (sum_rect - sum_lower) % MOD
        # Update row_prefix and prefix
        row_prefix[i][j] = (row_prefix[i][j-1] + dp[i][j]) % MOD
        prefix[i][j] = (prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + dp[i][j]) % MOD

print(dp[H][W] % MOD)
0