結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー | susami-jpg |
提出日時 | 2022-03-16 12:30:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,637 ms / 5,000 ms |
コード長 | 2,246 bytes |
コンパイル時間 | 425 ms |
コンパイル使用メモリ | 81,636 KB |
実行使用メモリ | 369,300 KB |
最終ジャッジ日時 | 2023-10-24 17:16:04 |
合計ジャッジ時間 | 10,380 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,496 KB |
testcase_01 | AC | 44 ms
55,496 KB |
testcase_02 | AC | 63 ms
76,652 KB |
testcase_03 | AC | 150 ms
94,748 KB |
testcase_04 | AC | 1,001 ms
298,264 KB |
testcase_05 | AC | 57 ms
65,932 KB |
testcase_06 | AC | 44 ms
55,564 KB |
testcase_07 | AC | 2,637 ms
369,300 KB |
testcase_08 | AC | 71 ms
55,452 KB |
testcase_09 | AC | 525 ms
196,696 KB |
testcase_10 | AC | 52 ms
65,848 KB |
testcase_11 | AC | 283 ms
133,424 KB |
testcase_12 | AC | 312 ms
142,784 KB |
testcase_13 | AC | 306 ms
134,468 KB |
testcase_14 | AC | 109 ms
97,400 KB |
testcase_15 | AC | 279 ms
128,092 KB |
testcase_16 | AC | 401 ms
157,380 KB |
testcase_17 | AC | 89 ms
82,344 KB |
testcase_18 | AC | 1,251 ms
272,552 KB |
testcase_19 | AC | 337 ms
146,276 KB |
testcase_20 | AC | 94 ms
84,260 KB |
testcase_21 | AC | 149 ms
101,176 KB |
testcase_22 | AC | 171 ms
96,684 KB |
testcase_23 | AC | 72 ms
79,480 KB |
testcase_24 | AC | 127 ms
94,960 KB |
ソースコード
from sys import exit, stdin, setrecursionlimit from bisect import bisect_left, bisect_right, insort_left, insort_right from collections import defaultdict, deque, Counter from heapq import heappop, heappush, heapify #from itertools import permutations, combinations, accumulate #from math import sqrt, factorial #math.log(x, y)はyを底としたxの対数を返す。 #数学ではlogとかlnで表される自然対数(ネイピア数eを底とする対数)は、math.log(x)で計算できる。 #二進対数(2を底とする対数)は、math.log2(x)で計算できる。math.log(x, 2)よりも正確な値となる。 #常用対数(10を底とする対数)は、math.log10(x)で計算できる。math.log(x, 10)よりも正確な値となる。 #from decimal import Decimal, ROUND_HALF_UP #decimalには文字列で渡す PyPyは遅いのでPython3で提出する #d1 = Decimal('1.1') d2 = Decimal('2.3') -> d1 + d2などの演算で浮動小数点数での誤差がなくなる(割り算もok) #四捨五入: dをDecimalオブジェクトとして、d.quantize(Decimal('1'), rounding=ROUND_HALF_UP)) (1にすると整数を返し、0.1にすると小数第一位で四捨五入) INF = 10**18 MOD = 10**9+7 MOD2 = 998244353 eps = 0.0000000001 setrecursionlimit(10**7) #pypyでの再帰TLE対策(自分の環境では使えないので提出時のみコメントアウトするように注意) import pypyjit pypyjit.set_param('max_unroll_recursion=-1') #list複数行読み込み高速化 改行、空白区切り注意 #[list(map(int, stdin.readline().split())) for _ in range(M)] #複数行読み込み 行ごとに文字列として読み込む ex) ['9 2 6 5 3', '改行', '5 8 9 7 9', '改行'] 改行区切りなのと空白区切りをsplitする必要があるので注意 #query = stdin.readlines() N, S, K = map(int, input().split()) #dfs(i, T):= i番目の支払金額まで決まっていて、残額がT円の時の支払う場合の数 rec = dict() def dfs(i, T): if (i, T) in rec:return rec[(i, T)] if T < 0:return 0 if i == 1: if T%N == 0:return 1 else:return 0 res = dfs(i-1, T-(N-i+1)*K) + dfs(i, T-(N-i+1)) res %= MOD rec[(i, T)] = res return res print(dfs(N, S))