結果
問題 | No.1111 コード進行 |
ユーザー | McGregorsh |
提出日時 | 2023-07-12 21:58:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,323 ms / 2,000 ms |
コード長 | 1,840 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 87,028 KB |
実行使用メモリ | 310,524 KB |
最終ジャッジ日時 | 2023-10-12 11:59:29 |
合計ジャッジ時間 | 20,431 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 243 ms
91,096 KB |
testcase_01 | AC | 239 ms
91,092 KB |
testcase_02 | AC | 234 ms
89,984 KB |
testcase_03 | AC | 236 ms
90,016 KB |
testcase_04 | AC | 240 ms
90,272 KB |
testcase_05 | AC | 247 ms
90,896 KB |
testcase_06 | AC | 263 ms
96,352 KB |
testcase_07 | AC | 256 ms
91,104 KB |
testcase_08 | AC | 250 ms
91,152 KB |
testcase_09 | AC | 248 ms
91,492 KB |
testcase_10 | AC | 262 ms
98,076 KB |
testcase_11 | AC | 252 ms
91,060 KB |
testcase_12 | AC | 255 ms
91,056 KB |
testcase_13 | AC | 253 ms
91,360 KB |
testcase_14 | AC | 289 ms
98,620 KB |
testcase_15 | AC | 249 ms
91,488 KB |
testcase_16 | AC | 261 ms
96,892 KB |
testcase_17 | AC | 256 ms
98,380 KB |
testcase_18 | AC | 246 ms
91,184 KB |
testcase_19 | AC | 241 ms
91,300 KB |
testcase_20 | AC | 245 ms
91,376 KB |
testcase_21 | AC | 240 ms
91,188 KB |
testcase_22 | AC | 265 ms
100,508 KB |
testcase_23 | AC | 250 ms
91,420 KB |
testcase_24 | AC | 250 ms
91,396 KB |
testcase_25 | AC | 278 ms
100,056 KB |
testcase_26 | AC | 255 ms
91,272 KB |
testcase_27 | AC | 243 ms
91,048 KB |
testcase_28 | AC | 401 ms
201,384 KB |
testcase_29 | AC | 331 ms
139,020 KB |
testcase_30 | AC | 386 ms
163,896 KB |
testcase_31 | AC | 270 ms
103,608 KB |
testcase_32 | AC | 428 ms
158,880 KB |
testcase_33 | AC | 512 ms
133,700 KB |
testcase_34 | AC | 358 ms
171,156 KB |
testcase_35 | AC | 393 ms
194,016 KB |
testcase_36 | AC | 759 ms
200,304 KB |
testcase_37 | AC | 399 ms
120,372 KB |
testcase_38 | AC | 354 ms
112,588 KB |
testcase_39 | AC | 510 ms
162,728 KB |
testcase_40 | AC | 626 ms
191,956 KB |
testcase_41 | AC | 455 ms
214,048 KB |
testcase_42 | AC | 492 ms
142,928 KB |
testcase_43 | AC | 491 ms
135,244 KB |
testcase_44 | AC | 318 ms
116,240 KB |
testcase_45 | AC | 437 ms
166,616 KB |
testcase_46 | AC | 266 ms
99,064 KB |
testcase_47 | AC | 1,323 ms
310,524 KB |
testcase_48 | AC | 266 ms
98,592 KB |
testcase_49 | AC | 268 ms
98,680 KB |
ソースコード
import sys from sys import stdin from fractions import Fraction import math from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from decimal import Decimal, getcontext, ROUND_HALF_UP def i_input(): return int(stdin.readline()) def i_map(): return map(int, stdin.readline().split()) def i_list(): return list(i_map()) def s_input(): return stdin.readline()[:-1] def s_map(): return s_input().split() def s_list(): return list(s_map()) def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 alpa = 'abcdefghijklmnopqrstuvwxyz' ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' def main(): N, M, K = i_map() G = [[] for i in range(300)] for i in range(M): p, q, c = i_map() p -= 1 q -= 1 G[p].append([q, c]) dp = [[[0] * (K+1) for i in range(300)] for i in range(N)] for i in range(300): dp[0][i][0] = 1 for i in range(N-1): for j in range(300): for k in range(K+1): for nxt, cost in G[j]: if k + cost <= K: dp[i+1][nxt][k+cost] += dp[i][j][k] dp[i+1][nxt][k+cost] %= MOD ans = 0 for i in range(300): ans += dp[-1][i][-1] ans %= MOD print(ans) if __name__ == '__main__': main()