結果
問題 | No.1037 exhausted |
ユーザー | tcltk |
提出日時 | 2021-01-18 01:38:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 460 ms / 2,000 ms |
コード長 | 1,519 bytes |
コンパイル時間 | 287 ms |
コンパイル使用メモリ | 87,304 KB |
実行使用メモリ | 118,980 KB |
最終ジャッジ日時 | 2023-08-20 07:43:33 |
合計ジャッジ時間 | 9,020 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 259 ms
83,256 KB |
testcase_01 | AC | 256 ms
83,584 KB |
testcase_02 | AC | 254 ms
83,648 KB |
testcase_03 | AC | 259 ms
83,616 KB |
testcase_04 | AC | 253 ms
83,608 KB |
testcase_05 | AC | 254 ms
83,608 KB |
testcase_06 | AC | 256 ms
83,444 KB |
testcase_07 | AC | 255 ms
83,256 KB |
testcase_08 | AC | 257 ms
83,624 KB |
testcase_09 | AC | 255 ms
83,440 KB |
testcase_10 | AC | 255 ms
83,540 KB |
testcase_11 | AC | 259 ms
83,456 KB |
testcase_12 | AC | 428 ms
118,896 KB |
testcase_13 | AC | 426 ms
118,756 KB |
testcase_14 | AC | 456 ms
118,912 KB |
testcase_15 | AC | 460 ms
118,496 KB |
testcase_16 | AC | 450 ms
118,284 KB |
testcase_17 | AC | 454 ms
118,980 KB |
testcase_18 | AC | 449 ms
118,840 KB |
testcase_19 | AC | 457 ms
118,512 KB |
testcase_20 | AC | 265 ms
83,620 KB |
testcase_21 | AC | 261 ms
83,672 KB |
testcase_22 | AC | 278 ms
83,588 KB |
ソースコード
#region Header #!/usr/bin/env python3 # from typing import * import sys import io import math import collections import decimal import itertools from queue import PriorityQueue import bisect import heapq def input(): return sys.stdin.readline()[:-1] sys.setrecursionlimit(1000000) #endregion # _INPUT = """5 8 11 # 2 2 231985796 # 6 0 190979457 # 7 2 373925694 # 8 2 976892608 # 8 1 184831039 # """ # sys.stdin = io.StringIO(_INPUT) def main(): N, V, L = map(int, input().split()) x = [0] + [None for _ in range(N)] + [L] v = [0] + [None for _ in range(N)] + [0] w = [0] + [None for _ in range(N)] + [0] for i in range(N): x[i+1], v[i+1], w[i+1] = map(int, input().split()) if x[i+1] - x[i] > V: print(-1) return if x[N+1] - x[N] > V: print(-1) return dp = [[10**10 for _ in range(V+1)] for _ in range(N+2)] dp[0][V] = 0 for i in range(N+1): d = x[i+1] - x[i] for v1 in range(V+1): if dp[i][v1] < 10**10: if v1-(x[i+1]-x[i]) >= 0: dp[i+1][v1-d] = min(dp[i+1][v1-d], dp[i][v1]) v_filled = min(v1+v[i], V) if v_filled - d >= 0: dp[i+1][v_filled-d] = min(dp[i+1][v_filled-d], dp[i][v1] + w[i]) MinW = min(dp[N+1]) if MinW == 10**10: print(-1) else: print(MinW) if __name__ == '__main__': main()