結果
問題 | No.914 Omiyage |
ユーザー | McGregorsh |
提出日時 | 2023-07-09 22:17:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 1,647 bytes |
コンパイル時間 | 642 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 89,280 KB |
最終ジャッジ日時 | 2024-07-23 19:52:12 |
合計ジャッジ時間 | 5,281 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 144 ms
88,928 KB |
testcase_01 | AC | 142 ms
89,072 KB |
testcase_02 | AC | 140 ms
88,624 KB |
testcase_03 | AC | 143 ms
89,212 KB |
testcase_04 | AC | 139 ms
89,024 KB |
testcase_05 | AC | 135 ms
88,464 KB |
testcase_06 | AC | 135 ms
88,424 KB |
testcase_07 | AC | 136 ms
88,600 KB |
testcase_08 | AC | 134 ms
88,488 KB |
testcase_09 | AC | 138 ms
88,352 KB |
testcase_10 | AC | 139 ms
88,492 KB |
testcase_11 | AC | 135 ms
88,472 KB |
testcase_12 | AC | 146 ms
89,192 KB |
testcase_13 | AC | 142 ms
89,032 KB |
testcase_14 | AC | 144 ms
89,280 KB |
testcase_15 | AC | 136 ms
88,788 KB |
testcase_16 | AC | 137 ms
88,564 KB |
testcase_17 | AC | 139 ms
88,856 KB |
testcase_18 | AC | 139 ms
88,548 KB |
testcase_19 | AC | 135 ms
88,332 KB |
testcase_20 | AC | 140 ms
88,092 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() A = [i_list() for i in range(N)] dp = [[False] * (K+1) for i in range(N+1)] dp[0][0] = True for i in range(N): for j in range(K+1): if dp[i][j]: for k in range(M): if j + A[i][k] <= K: dp[i+1][j+A[i][k]] = True for i in range(K, -1, -1): if dp[-1][i]: print(K-i) exit() print(-1) if __name__ == '__main__': main()