結果

問題 No.612 Move on grid
ユーザー lam6er
提出日時 2025-03-20 21:17:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 773 ms / 2,500 ms
コード長 1,061 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 108,536 KB
最終ジャッジ日時 2025-03-20 21:18:29
合計ジャッジ時間 7,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    a, b, c, d, e = map(int, input[ptr:ptr+5])
    ptr +=5
    
    mod = 10**9 +7
    delta_options = [a, -a, b, -b, c, -c]
    offset = 10000  # since T*max_abs_delta (20*500=10000)
    
    current = [0] * (2 * offset +1)
    current[offset] = 1  # initial sum 0
    
    for _ in range(T):
        next_dp = [0] * (2 * offset +1)
        for s in range(2 * offset +1):
            if current[s] ==0:
                continue
            for delta in delta_options:
                new_s_real = (s - offset) + delta
                if -offset <= new_s_real <= offset:
                    new_s = new_s_real + offset
                    next_dp[new_s] = (next_dp[new_s] + current[s]) % mod
        current = next_dp
    
    result = 0
    for s in range(2 * offset +1):
        sum_val = s - offset
        if d <= sum_val <= e:
            result = (result + current[s]) % mod
    
    print(result % mod)

if __name__ == "__main__":
    main()
0