結果
問題 |
No.1163 I want to be a high achiever
|
ユーザー |
|
提出日時 | 2022-02-23 13:40:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 401 ms / 2,000 ms |
コード長 | 716 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 158,712 KB |
最終ジャッジ日時 | 2024-07-01 13:28:38 |
合計ジャッジ時間 | 6,696 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
N,X = map(int,input().split()) A = list(map(int,input().split())) B = list(map(int,input().split())) import sys flag = False for a in A: if a >= X: flag = True break if not flag: print(-1) exit() now = 0 C = [] D = [] for i in range(N): now += A[i] - X if A[i] < X: C.append(X-A[i]) D.append(B[i]) if now >= 0: print(0) exit() now = -now inf = 10 ** 8 N = len(D) dp = [[inf] * (now+1) for _ in range(N)] A = C B = D dp[0][min(now,A[0])] = B[0] dp[0][0] = 0 for i in range(N-1): for j in range(now+1): dp[i+1][j] = min(dp[i+1][j],dp[i][j]) dp[i+1][min(now,j+A[i+1])] = min(dp[i+1][min(now,j+A[i+1])],dp[i][j] + B[i+1]) print(dp[-1][-1])