結果

問題 No.110 しましまピラミッド
ユーザー lam6er
提出日時 2025-03-20 20:29:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 128 ms / 5,000 ms
コード長 1,526 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 85,876 KB
最終ジャッジ日時 2025-03-20 20:29:57
合計ジャッジ時間 2,671 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
from functools import lru_cache

def main():
    Nw = int(sys.stdin.readline())
    W = list(map(int, sys.stdin.readline().split()))
    W.sort(reverse=True)  # Sort white blocks in descending order

    Nb = int(sys.stdin.readline())
    B = list(map(int, sys.stdin.readline().split()))
    B.sort(reverse=True)  # Sort black blocks in descending order

    @lru_cache(maxsize=None)
    def dfs(next_color, prev_len, used_w, used_b):
        max_h = 0
        if next_color == 0:  # Next color is white
            for i in range(len(W)):
                if not (used_w & (1 << i)) and W[i] < prev_len:
                    new_used_w = used_w | (1 << i)
                    current_h = 1 + dfs(1, W[i], new_used_w, used_b)
                    if current_h > max_h:
                        max_h = current_h
        else:  # Next color is black
            for i in range(len(B)):
                if not (used_b & (1 << i)) and B[i] < prev_len:
                    new_used_b = used_b | (1 << i)
                    current_h = 1 + dfs(0, B[i], used_w, new_used_b)
                    if current_h > max_h:
                        max_h = current_h
        return max_h

    max_height = 0

    # Start with white
    for i in range(len(W)):
        h = 1 + dfs(1, W[i], 1 << i, 0)
        max_height = max(max_height, h)

    # Start with black
    for i in range(len(B)):
        h = 1 + dfs(0, B[i], 0, 1 << i)
        max_height = max(max_height, h)

    print(max_height)

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