結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー shout_poorshout_poor
提出日時 2017-04-05 13:01:35
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 1,332 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 135,656 KB
最終ジャッジ日時 2024-07-08 10:34:30
合計ジャッジ時間 4,076 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import resource
from copy import copy

# Question: https://yukicoder.me/problems/no/498

DIV_CONST = 1000000007


def trace(goal_x, goal_y, crystals):

    memo = {}

    def local_iter(node):
        if node not in memo:
            (x, y, remain_crystals) = node
            count = 1 if (x, y) == (goal_x, goal_y) else 0
            for crystal in remain_crystals:
                next_x = x + crystal[0]
                next_y = y + crystal[1]
                next_remains = remain_crystals - {crystal}
                if crystal[2] > 1:
                    next_remains = next_remains \
                                   | {(crystal[0], crystal[1], crystal[2] - 1)}
                count = count + local_iter((next_x, next_y, next_remains))

            memo[node] = count

        return memo[node]

    return local_iter((0, 0, crystals))


def load_input(crystal_kinds):
    for l in range(crystal_kinds):
        [x, y, num] = [int(s) for s in raw_input().split()]
        yield (x, y, num)


if __name__ == '__main__':
    # from time import time
    [goal_x, goal_y, crystal_kinds] = [int(s) for s in raw_input().split()]
    # start_time = time()
    crystals = frozenset(load_input(crystal_kinds))
    # proc_time = time() - start_time
    print trace(goal_x, goal_y, crystals)
    # print "time: %f[sec]" % proc_time
0