結果

問題 No.2003 Frog on Grid
ユーザー qwewe
提出日時 2025-04-24 12:31:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,825 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 81,916 KB
実行使用メモリ 105,224 KB
最終ジャッジ日時 2025-04-24 12:33:10
合計ジャッジ時間 5,978 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)]

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[1][1] = 1 if grid[0][0] == '.' else 0

# Initialize row_prefix for each row
row_prefix = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
    current_prefix = [0] * (W + 1)
    for j in range(1, W + 1):
        current_prefix[j] = (current_prefix[j-1] + dp[i][j]) % MOD
    row_prefix[i] = current_prefix

for i in range(1, H + 1):
    current_row_prefix = [0] * (W + 1)
    for j in range(1, W + 1):
        if i == 1 and j == 1:
            current_row_prefix[j] = dp[i][j]
            continue
        if grid[i-1][j-1] == '#':
            dp[i][j] = 0
            current_row_prefix[j] = (current_row_prefix[j-1] + dp[i][j]) % MOD
            continue
        
        total = 0
        for a in range(0, min(K, i-1) + 1):
            x = i - a
            remaining = K - a
            if remaining < 0:
                continue
            min_j = max(1, j - remaining)
            if min_j > j:
                continue
            if x < 1:
                continue
            
            if x < i:
                # Use precomputed row_prefix for previous rows
                sum_val = (row_prefix[x][j] - row_prefix[x][min_j - 1]) % MOD
            else:
                # Current row, use current_row_prefix which is built up to j-1
                sum_val = (current_row_prefix[j-1] - (current_row_prefix[min_j - 1] if min_j > 1 else 0)) % MOD
            
            total = (total + sum_val) % MOD
        
        dp[i][j] = total % MOD
        current_row_prefix[j] = (current_row_prefix[j-1] + dp[i][j]) % MOD
    
    # Update the row_prefix for this row after processing all columns
    row_prefix[i] = current_row_prefix

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