結果

問題 No.584 赤、緑、青の色塗り
ユーザー lam6er
提出日時 2025-03-31 17:37:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,669 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 288,036 KB
最終ジャッジ日時 2025-03-31 17:37:56
合計ジャッジ時間 5,244 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    R = int(data[1])
    G = int(data[2])
    B = int(data[3])
    
    if R + G + B > N:
        print(0)
        return
    
    from collections import defaultdict
    prev = defaultdict(int)
    
    prev[(None, None, R, G, B)] = 1
    
    for _ in range(N):
        curr = defaultdict(int)
        for (p0, p1, r, g, b), cnt in prev.items():
            new_p0 = None
            new_p1 = p0
            curr_key = (new_p0, new_p1, r, g, b)
            curr[curr_key] = (curr[curr_key] + cnt) % MOD
            
            if r > 0 and p0 != 'R':
                if p0 is not None and p1 is not None:
                    continue
                new_r = r - 1
                curr_key = ('R', p0, new_r, g, b)
                curr[curr_key] = (curr[curr_key] + cnt) % MOD
            
            if g > 0 and p0 != 'G':
                if p0 is not None and p1 is not None:
                    continue
                new_g = g - 1
                curr_key = ('G', p0, r, new_g, b)
                curr[curr_key] = (curr[curr_key] + cnt) % MOD
            
            if b > 0 and p0 != 'B':
                if p0 is not None and p1 is not None:
                    continue
                new_b = b - 1
                curr_key = ('B', p0, r, g, new_b)
                curr[curr_key] = (curr[curr_key] + cnt) % MOD
        prev = curr
    
    total = 0
    for (p0, p1, r, g, b), cnt in prev.items():
        if r == 0 and g == 0 and b == 0:
            total = (total + cnt) % MOD
    print(total)

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