結果
問題 |
No.2542 Yokan for Two
|
ユーザー |
|
提出日時 | 2023-11-24 23:38:44 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 776 bytes |
コンパイル時間 | 471 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 904,320 KB |
最終ジャッジ日時 | 2024-09-26 09:49:32 |
合計ジャッジ時間 | 8,937 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 MLE * 1 |
other | AC * 1 MLE * 1 -- * 38 |
ソースコード
L, N = map(int, input().split()) X = [0] + list(map(int, input().split())) + [L] A = [] for i in range(N + 1): A.append(X[i + 1] - X[i]) N = len(A) M = 2 * L + 10 dp = [[[0] * 2 for _ in range(M)] for _ in range(N + 1)] dp[0][L][0] = 1 for i, a in enumerate(A): for j in range(M): for k in range(2): if not dp[i][j][k]: continue if not k: dp[i + 1][j + a][k] = 1 if i: dp[i + 1][j - a][1 - k] = 1 else: dp[i + 1][j - a][k] = 1 if i: dp[i + 1][j + a][1 - k] = 1 ans = 10 ** 18 for j in range(M): if dp[N][j][1]: ans = min(ans, abs(j - L)) print(ans) # for i in range(N + 1): # print(dp[i])